Entropy compression method applied to graph colorings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2014

Entropy compression method applied to graph colorings


Based on the algorithmic proof of Lov\'asz local lemma due to Moser and Tardos, Esperet and Parreau developed a framework to prove upper bounds for several chromatic numbers (in particular acyclic chromatic index, star chromatic number and Thue chromatic number) using the so-called \emph{entropy compression method}. Inspired by this work, we propose a more general framework and a better analysis. This leads to improved upper bounds on chromatic numbers and indices. In particular, every graph with maximum degree Δ has an acyclic chromatic number at most 32Δ43+O(Δ), and a non-repetitive chromatic number at most Δ2+1.89Δ53+O(Δ43). Also every planar graph with maximum degree Δ has a facial Thue chromatic number at most Δ+O(Δ12) and facial Thue chromatic index at most 10.
Fichier principal
Vignette du fichier
1406.4380.pdf (390.06 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01233456 , version 1 (04-02-2020)


  • HAL Id : lirmm-01233456 , version 1
  • ARXIV : 1406.4380


Daniel Gonçalves, Mickaël Montassier, Alexandre Pinlou. Entropy compression method applied to graph colorings. ICGT: International Colloquium on Graph Theory and Combinatorics, Jun 2014, Grenoble, France. ⟨lirmm-01233456⟩
206 View
58 Download



Gmail Mastodon Facebook X LinkedIn More