Acyclic edge-coloring using entropy compression

An edge-coloring of a graph GG is acyclic   if it is a proper edge-coloring of GG and every cycle contains at least three colors. We prove that every graph with maximum degree ΔΔ has an acyclic edge-coloring with at most 4Δ−44Δ−4 colors, improving the previous bound of ⌈9.62(Δ−1)⌉. Our bound results from the analysis of a very simple randomized procedure using the so-called entropy compression method  . We show that the expected running time of the procedure is O(mnΔ2logΔ)O(mnΔ2logΔ), where nn and mm are the number of vertices and edges of GG. Such a randomized procedure running in expected polynomial time was only known to exist in the case where at least 16Δ16Δ colors were available.Our aim here is to make a pedagogic tutorial on how to use these ideas to analyze a broad range of graph coloring problems. As an application, we also show that every graph with maximum degree ΔΔ has a star coloring with 22Δ3/2+Δ colors.