Acyclic edge-coloring using entropy compression

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 Δ has an acyclic edge-coloring with at most 4 Δ − 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 ( m n Δ 2 log Δ ) , where n and m are the number of vertices and edges of G . Such a randomized procedure running in expected polynomial time was only known to exist in the case where at least 16 Δ colors were available. m 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 2 2 Δ 3 / 2 + Δ colors.