
arXiv: 1412.6237
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 ��(G)+2$, where $��(G)$ denotes the maximum degree of $G$. The best known general bound is $a'(G)\leq 4(��(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��(G)+o(��(G))$. Moreover, for every $\varepsilon>0$, there exists a constant $c$ such that if $g(G)\geq c$, then $a'(G)\leq(2+\varepsilon)��(G)+o(��(G))$, where $g(G)$ denotes the girth of $G$.
12 pages, 2 figures. This version uses the Local Cut Lemma instead of the Local Action Lemma
Coloring of graphs and hypergraphs, Lovász local lemma, FOS: Mathematics, acyclic edge coloring, Mathematics - Combinatorics, Combinatorics (math.CO), local cut lemma
Coloring of graphs and hypergraphs, Lovász local lemma, FOS: Mathematics, acyclic edge coloring, Mathematics - Combinatorics, Combinatorics (math.CO), local cut lemma
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
