New Bounds for the Acyclic Chromatic Index
Abstract
An edge coloring of a graph $G$ is called an acyclic edge coloring if it is proper and every cycle in $G$ contains edges of at least three different colors. 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)$. Fiamčik and independently Alon, Sudakov, and Zaks conjectured that $a'(G) \leq \Delta(G)+2$, where $\Delta(G)$ denotes the maximum degree of $G$. 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ász Local 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$.
 Publication:

arXiv eprints
 Pub Date:
 December 2014
 arXiv:
 arXiv:1412.6237
 Bibcode:
 2014arXiv1412.6237B
 Keywords:

 Mathematics  Combinatorics
 EPrint:
 12 pages, 2 figures. This version uses the Local Cut Lemma instead of the Local Action Lemma