A note on acyclic vertex-colorings

Note sur la coloration acyclique des sommets d'un graphe

Jean-Sébastien Sereni (1) , Jan Volec (2)

1 ORPAILLEUR - Knowledge representation, reasonning
2 DIMAP - Centre for Discrete Mathematics and its Applications [Warwick]

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.

Mots clés: acyclic coloring; local lemma; entropy compression

Domaines: Combinatoire [math.CO]

Jean-Sébastien Sereni, Jan Volec. A note on acyclic vertex-colorings. Journal of Combinatorics, 2016, 7 (4), pp.725--737. ⟨10.4310/JOC.2016.v7.n4.a8⟩. ⟨hal-00921122⟩