Acyclic edge coloring of graphs
arXiv:1302.2405 · doi:10.1016/j.dam.2013.12.001
Abstract
An {\em acyclic edge coloring} of a graph 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 {\em acyclic chromatic index} $\chiup_{a}'(G)$ of a graph is the least number of colors needed in an acyclic edge coloring of . Fiamčík (1978) conjectured that $\chiup_{a}'(G) \leq Δ(G) + 2$, where is the maximum degree of . This conjecture is well known as Acyclic Edge Coloring Conjecture (AECC). A graph with maximum degree at most is {\em -deletion-minimal} if $\chiup_{a}'(G) > κ$ and $\chiup_{a}'(H) \leq κ$ for every proper subgraph of . 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 (\autoref{NMAD4}). 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 -cycle has at most three edges contained in triangles (\autoref{NoAdjacent}), from which we can conclude some known results as corollaries. We thirdly prove that every planar graph without intersecting triangles satisfies $\chiup_{a}'(G) \leq Δ(G) + 3$ (\autoref{NoIntersect}). Finally, we consider one extreme case and prove it: if is a graph with and all the -vertices are independent, then $\chiup_{a}'(G) = Δ(G)$. We hope the structural lemmas will shed some light on the acyclic edge coloring problems.
19 pages