Generalized acyclic edge colorings via entropy compression

An r-acyclic edge coloring of a graph G is a proper edge coloring such that any cycle C has at least $$\min \{|C|,r\}$$ min { | C | , r } colors. The least number of colors needed for an r-acyclic edge coloring of G is called the r-acyclic edge chromatic number or the r-acyclic chromatic index of G, denoted by $$A'_{r}\left( G\right) $$ A r ′ G . In this paper, we study the r-acyclic edge chromatic number with $$r\ge 4$$ r ≥ 4 and prove that $$A'_{r}\left( G\right) \le 2\Delta ^{\lfloor \tfrac{r}{2}\rfloor }+O\left( \Delta ^{\tfrac{r+1}{3}}\right) $$ A r ′ G ≤ 2 Δ ⌊ r 2 ⌋ + O Δ r + 1 3 . We also prove that when r is even, $$A'_{r}\left( G\right) \le \Delta ^{\tfrac{r}{2}}+O\left( \Delta ^{\tfrac{r+1}{3}}\right) $$ A r ′ G ≤ Δ r 2 + O Δ r + 1 3 , which is asymptotically optimal. In addition, we investigate how the r-acyclic edge chromatic number performs as the girth increases. It is proved in this paper that for every graph G with girth at least $$2r-1$$ 2 r - 1 , $$A'_r\left( G\right) \le \left( 9r-7\right) \Delta +10r-12$$ A r ′ G ≤ 9 r - 7 Δ + 10 r - 12 holds. Our approach is based on the entropy compression method.