Abstract:

If a proper edge coloring of G contains no bichromatic cycles in G, then it is an acyclic edge coloring of G. The acyclic chromatic number of G is the minimum number of colors among all the acyclic edge colorings of G. By using the properties of planar graphs that have been proposed, it is proved that if G is a 2-connected planar graph without 4-cycles, then its acyclic chromatic number is no more than Δ(G)+11.

Key words: acyclic edge coloring; planar graph; girth