A note on acyclic vertex-colorings

2013/12/19 by Jean‐Sébastien Sereni, Jean-Sébastien Sereni, Jan Volec +2 · 1 citation
Computer Science · Mathematics · #05C15 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05D40

paper · pdf · doi:10.48550/arxiv.1312.5600

arxiv created 2013/12/19 · openalex publication_date 2013/12/19 · arxiv updated 2013/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the acyclic chromatic number of a graph with maximum degree Δ is less than 2.835Δ^4/3+Δ. This improves the previous upper bound, which was 50Δ^4/3. To do so, we draw inspiration from works by Alon, McDiarmid and Reed and by Esperet and Parreau.

Cited by

• The Thue choice number versus the Thue chromatic number of graphs

Related

• An Improved Bound of Acyclic Vertex-Coloring
• A new bound on the acyclic edge chromatic index
• Acyclic Edge Coloring of Graphs with Maximum Degree 4
• Improved bounds for acyclic coloring parameters
• Improved bounds on coloring of graphs