Acyclic edge-coloring using entropy compression
arXiv:1206.1535 · doi:10.1016/j.ejc.2013.02.007
Abstract
An edge-coloring of a graph G is acyclic if it is a proper edge-coloring of G and every cycle contains at least three colors. We prove that every graph with maximum degree Delta has an acyclic edge-coloring with at most 4 Delta - 4 colors, improving the previous bound of 9.62 (Delta - 1). Our bound results from the analysis of a very simple randomised procedure using the so-called entropy compression method. We show that the expected running time of the procedure is O(mn Delta^2 log Delta), where n and m are the number of vertices and edges of G. Such a randomised procedure running in expected polynomial time was only known to exist in the case where at least 16 Delta colors were available. Our aim here is to make a pedagogic tutorial on how to use these ideas to analyse a broad range of graph coloring problems. As an application, also show that every graph with maximum degree Delta has a star coloring with 2 sqrt(2) Delta^{3/2} + Delta colors.
13 pages, revised version
References in corpus (2)
Cited by in corpus (27)
- Nonrepetitive Colouring via Entropy Compression
- The Johansson--Molloy Theorem for DP-Coloring
- The Local Cut Lemma
- Progress on the adjacent vertex distinguishing edge colouring conjecture
- Further result on acyclic chromatic index of planar graphs
- Proper Conflict-free Coloring of Graphs with Large Maximum Degree
- Acyclic edge coloring of graphs
- New Bounds for the Acyclic Chromatic Index
- An Introduction to the Discharging Method via Graph Coloring
- A local lemma via entropy compression
- An algorithmic framework for colouring locally sparse graphs
- A general framework for hypergraph colouring
- Acyclic chromatic index of triangle-free 1-planar graphs
- Acyclic edge colourings of graphs with large girth
- Entropy Compression Method and Legitimate Colorings in Projective Planes
- The Local Action Lemma
- A new bound on the acyclic edge chromatic index
- The Acyclic Chromatic Index is Less than the Double of the Max Degree
- Nonrepetitive graph colouring
- A note on acyclic vertex-colorings
- Uniquely restricted matchings and edge colorings
- On harmonious coloring of hypergraphs
- Counting colorings of triangle-free graphs
- Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
- Witness trees in the Moser-Tardos algorithmic Lovász Local Lemma and Penrose trees in the hard core lattice gas
- Acyclic colourings of graphs with obstructions
- A constructive algorithm for the LLL on permutations