Acyclic Edge Coloring of 1-Tree and Outerplane Graphs
Zhenyu Xu · 2004
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. N. Alon conjectured that a′(G)≤△+2 for all graphs G where △ is the maximum degree in G.This paper proved that the conjecture holds for 1-tree and outerplane graphs, whose acyclic edge chromatic numbers do not exceed △+1 .