Entropy compression method applied to graph colorings

MaRDI QIDQ6252410zbMATH OpenFDO

Authors Daniel Gonçalves, Mickaël Montassier, Alexandre Pinlou

Publication date 17 June 2014

Abstract: Based on the algorithmic proof of Lov'asz local lemma due to Moser and Tardos, the works of Grytczuk et al. on words, and Dujmovi'c et al. on colorings, 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 $Delta$ has an acyclic chromatic number at most $frac32Delt{a}^{frac43}+O(Delta)$. Also every planar graph with maximum degree $Delta$ has a facial Thue choice number at most $Delta+O(Delt{a}^{f}rac12)$ and facial Thue choice index at most $10$.

This page was built for publication: Entropy compression method applied to graph colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6252410)