The acyclic edge chromatic number of a random d‐regular graph is d + 1

DOI10.1002/JGT.20064MaRDI QIDQ4680406zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, Nicholas Wormald

Publication date 1 June 2005

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.20064

zbMATH Keywords

acyclic coloringcoloringedge coloringrandom graphsregular graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• The generalized acyclic edge chromatic number of random regular graphs
• Acyclic edge colorings of graphs
• Colouring Random Regular Graphs
• d‐Regular graphs of acyclic chromatic index at least d+2
• On the chromatic number of random \(d\)-regular graphs

Cites work

• An algorithmic approach to the Lovász local lemma. I
• Automorphisms of Dowling Lattices and Related Geometries
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)

Cited in

(28)

• A note on acyclic edge coloring of complete bipartite graphs
• Generalized acyclic edge colorings via entropy compression
• Acyclic edge coloring of planar graphs without 4-cycles
• Acyclic edge coloring of IC-planar graphs
• Local conditions for planar graphs of acyclic edge coloring
• Acyclic chromatic indices of planar graphs with large girth
• Acyclic edge coloring of planar graphs without adjacent cycles
• Bounds on the generalised acyclic chromatic numbers of bounded degree graphs
• An algorithm for optimal acyclic edge-colouring of cubic graphs
• Acyclic edge coloring of 2-degenerate graphs
• The generalized acyclic edge chromatic number of random regular graphs
• Acyclic edge coloring of planar graphs without 5-cycles
• Acyclic chromatic indices of planar graphs with girth at least five
• Randomly colouring graphs (a combinatorial view)
• The cook-book approach to the differential equation method
• Acyclic list edge coloring of graphs
• On acyclic edge-coloring of the complete bipartite graphs \(K_{2p-1, 2p-1}\) for odd prime \(p\)
• Acyclic list edge coloring of graphs with maximum degree 4
• d‐Regular graphs of acyclic chromatic index at least d+2
• Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4
• Acyclic and tree unique colourings in random graphs
• Acyclic chromatic index of IC-planar graphs
• Optimal acyclic edge colouring of grid like graphs
• Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs
• On acyclic edge-coloring of complete bipartite graphs
• Acyclic edge coloring of triangle-free 1-planar graphs
• Analysis of a heuristic for acyclic edge colouring
• Acyclic edge coloring of subcubic graphs

This page was built for publication: The acyclic edge chromatic number of a random d‐regular graph is d + 1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4680406)