Skip to Main content Skip to Navigation
Journal articles

Acyclic coloring of graphs and entropy compression method

Daniel Gonçalves 1 Mickaël Montassier 1 Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, Dujmović et al. (2016) initiated the use of the so-called entropy compression method for graph coloring problems. Then, using the same approach Esperet and Parreau (2013) proved new upper bounds for several chromatic numbers, and explained how that approach could be used for many different coloring problems. Here, we follow this line of research for the particular case of acyclic coloring: we show that every graph with maximum degree \Delta has acyclic chromatic number at most \frac{3}{2}\Delta^\frac{4}{3}+0(\Delta).
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02938618
Contributor : Alexandre Pinlou <>
Submitted on : Tuesday, December 15, 2020 - 2:21:34 PM
Last modification on : Tuesday, December 15, 2020 - 2:24:28 PM
Long-term archiving on: : Tuesday, March 16, 2021 - 7:39:23 PM

Identifiers

Collections

Citation

Daniel Gonçalves, Mickaël Montassier, Alexandre Pinlou. Acyclic coloring of graphs and entropy compression method. Discrete Mathematics, Elsevier, 2020, 343 (4), pp.#111772. ⟨10.1016/j.disc.2019.111772⟩. ⟨lirmm-02938618⟩

Share

Metrics

Record views

86

Files downloads

38