Paper Info
Title
The generalized acyclic edge chromatic number of random regular graphs
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 Research partly carried out while the author visited the Department of Mathematics and Statistics, University of Melbourne. Research supported by an Australian Research Council Postdoctoral Fellowship and by the UNSW Faculty Research Grants Scheme. Research partly carried out while the author was a member of the Department of Mathematics and Statistics, University of Melbourne. Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was a member of the Department of Mathematics and Statistics, University of Melbourne.
Year
DOI
Venue
2006
10.1002/jgt.v53:2
Journal of Graph Theory
Keywords
Field
DocType
regular graph,edge coloring,random graphs,upper bound
Discrete mathematics,Edge coloring,Combinatorics,Fractional coloring,Graph factorization,List coloring,Foster graph,Brooks' theorem,Moser spindle,Mathematics,Graph coloring
Journal
Volume
Issue
ISSN
53
2
0364-9024
Citations 
PageRank 
References 
5
0.52
10
Authors
3
Name
Order
Citations
PageRank
Stefanie Gerke119931.63
Catherine Greenhill262862.40
Nicholas C. Wormald31506230.43