Acyclic Edge Coloring of Planar Graphs Without Small Cycles

摘要

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ≤ Δ(G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles.