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

DOI10.1002/JGT.20064zbMath1062.05062OpenAlexW4235275672MaRDI QIDQ4680406

Jaroslav Nešetřil, Nicholas C. 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

random graphsedge coloringregular graphscoloringacyclic coloring

Mathematics Subject Classification ID

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

Related Items (23)

Local conditions for planar graphs of acyclic edge coloring ⋮ Analysis of a heuristic for acyclic edge colouring ⋮ Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4 ⋮ Acyclic edge coloring of planar graphs without 5-cycles ⋮ Acyclic chromatic indices of planar graphs with girth at least five ⋮ Acyclic edge coloring of planar graphs without 4-cycles ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Acyclic edge coloring of planar graphs without adjacent cycles ⋮ The cook-book approach to the differential equation method ⋮ Unnamed Item ⋮ An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs ⋮ On acyclic edge-coloring of the complete bipartite graphs \(K_{2p-1, 2p-1}\) for odd prime \(p\) ⋮ Generalized acyclic edge colorings via entropy compression ⋮ Acyclic List Edge Coloring of Graphs ⋮ Bounds on the generalised acyclic chromatic numbers of bounded degree graphs ⋮ Optimal acyclic edge colouring of grid like graphs ⋮ Acyclic edge coloring of IC-planar graphs ⋮ Acyclic chromatic indices of planar graphs with large girth ⋮ On acyclic edge-coloring of complete bipartite graphs ⋮ Acyclic edge coloring of subcubic graphs ⋮ Acyclic edge coloring of triangle-free 1-planar graphs ⋮ Acyclic edge coloring of 2-degenerate graphs ⋮ A note on acyclic edge coloring of complete bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• An algorithmic approach to the Lovász local lemma. I
• Automorphisms of Dowling Lattices and Related Geometries

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