𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The generalized acyclic edge chromatic number of random regular graphs

✍ Scribed by Stefanie Gerke; Catherine Greenhill; Nicholas Wormald

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
224 KB
Volume
53
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (rβ€‰βˆ’β€‰2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r β‰₯ 4 and d β‰₯ 2. Β© 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006

πŸ“œ SIMILAR VOLUMES

The acyclic edge chromatic number of a r
The acyclic edge chromatic number of a random d-regular graph is d + 1
✍ Jaroslav NeΕ‘etΕ™il; Nicholas C. Wormald πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 67 KB πŸ‘ 1 views

## Abstract We prove the theorem from the title: the acyclic edge chromatic number of a random __d__‐regular graph is asymptotically almost surely equal to __d__ + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Ξ”(G) + 2 is the bound for the a

Acyclic edge chromatic number of outerpl
Acyclic edge chromatic number of outerplanar graphs
✍ Jian-Feng Hou; Jian-Liang Wu; Gui-Zhen Liu; Bin Liu πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 176 KB

## Abstract A proper edge coloring of a graph __G__ is called acyclic if there is no 2‐colored cycle in __G__. The acyclic edge chromatic number of __G__, denoted by Ο‡(__G__), is the least number of colors in an acyclic edge coloring of __G__. In this paper, we determine completely the acyclic edge

On the chromatic number of a random 5-re
On the chromatic number of a random 5-regular graph
✍ J. DΓ­az; A. C. Kaporis; G. D. Kemkes; L. M. Kirousis; X. PΓ©rez; N. Wormald πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 275 KB πŸ‘ 1 views

## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is as

The independence number of an edge-chrom
The independence number of an edge-chromatic critical graph
✍ Douglas R. Woodall πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 77 KB πŸ‘ 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro

Acyclic graph coloring and the complexit
Acyclic graph coloring and the complexity of the star chromatic number
✍ David R. Guichard πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 294 KB

## Abstract Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, β€œWhen is Ο‡\* < Ο‡?” We show that Ο‡\* < Ο‡ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not i