New Bounds for the Acyclic Chromatic Index

Anton Bernshteyn

Published 2014-12-19Version 1

An edge coloring of a graph $G$ is called an acyclic edge coloring if it is proper (i.e. adjacent edges receive different colors) and every cycle in $G$ contains edges of at least three different colors (there are no bichromatic cycles in $G$). The least number of colors needed for an acyclic edge coloring of $G$ is called the acyclic chromatic index of $G$ and is denoted by $a'(G)$. It is conjectured by Fiam\v{c}ik and independently by Alon et al. that $a'(G) \leq \Delta(G)+2$, where $\Delta(G)$ denotes the maximum degree of $G$. However, the best known general bound is $a'(G)\leq 4(\Delta(G)-1)$ due to Esperet and Parreau. We apply a generalization of the Lov\'{a}sz Local Lemma that we call the Local Action Lemma to show that if $G$ contains no copy of a given bipartite graph $H$, then $a'(G) \leq 3\Delta(G)+o(\Delta(G))$. Moreover, for every $\varepsilon>0$ there exists a constant $c$ such that if $g(G)\geq c$, then $a'(G)\leq(2+\varepsilon)\Delta(G)+o(\Delta(G))$, where $g(G)$ denotes the girth of $G$.