Acyclic edge coloring of graphs

An acyclic edge coloring   of a graph GG is a proper edge coloring such that the subgraph induced by any two color classes is a linear forest (an acyclic graph with maximum degree at most two). The acyclic chromatic index  χa′(G) of a graph GG is the least number of colors needed in an acyclic edge coloring of GG. Fiamčík (1978) conjectured that χa′(G)≤Δ(G)+2, where Δ(G)Δ(G) is the maximum degree of GG. This conjecture is well known as the Acyclic Edge Coloring Conjecture (AECC). A graph GG with maximum degree at most κκ is κκ-deletion-minimal   if χa′(G)>κ and χa′(H)≤κ for every proper subgraph HH of GG. The purpose of this paper is to provide many structural lemmas on κκ-deletion-minimal graphs. By using the structural lemmas, we firstly prove that AECC is true for the graphs with maximum average degree less than four (Theorem 4.3). We secondly prove that AECC is true for the planar graphs without triangles adjacent to cycles of length at most four, with an additional condition that every 55-cycle has at most three edges contained in triangles (Theorem 4.4), from which we can conclude some known results as corollaries. We thirdly prove that every planar graph GG without intersecting triangles satisfies χa′(G)≤Δ(G)+3 (Theorem 4.6). Finally, we consider one extreme case and prove it: if GG is a graph with Δ(G)≥3Δ(G)≥3 and all the 3+3+-vertices are independent, then χa′(G)=Δ(G). We hope the structural lemmas will shed some light on the acyclic edge coloring problems.