Entropy compression method applied to graph colorings

Abstract

Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, the works of Grytczuk et al. on words, and Dujmović 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 $\frac{3}{2}{\Delta }^{\frac{4}{3}}+O(\Delta )$. Also every planar graph with maximum degree $\Delta$ has a facial Thue choice number at most $\Delta +O({\Delta }^{\frac{1}{2}})$ and facial Thue choice index at most $10$.

33 pages

References in corpus (3)

• On the facial Thue choice index via entropy compression
• Vertex coloring of plane graphs with nonrepetitive boundary paths
• List Colouring Squares of Planar Graphs

Cited by in corpus (11)

• The Local Cut Lemma
• A local lemma via entropy compression
• A general framework for hypergraph colouring
• The Local Action Lemma
• Entropy Compression Method and Legitimate Colorings in Projective Planes
• A new bound on the acyclic edge chromatic index
• The Thue choice number versus the Thue chromatic number of graphs
• Asymptotic size of covering arrays: an application of entropy compression
• An interactive version of the Lovász local lemma
• Compressibility and probabilistic proofs
• Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge