摘要
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. For planar graphs G with girth g(G), we prove that a (G) max{2Δ(G) + 2, Δ(G) + 22} if g(G) 3, a (G) Δ(G) + 2 if g(G) 5, a (G) Δ(G) + 1 if g(G) 7, and a (G) = Δ(G) if g(G) 16 and Δ(G) 3. For series-parallel graphs G, we have a (G) Δ(G) + 1.
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. For planar graphs G with girth g(G), we prove that a′(G) ? max{2Δ(G) ? 2, Δ(G) + 22} if g(G) ? 3, a′(G) ? Δ(G) + 2 if g(G) ? 5, a′(G) ? Δ(G) + 1 if g(G) ? 7, and a′(G) = Δ(G) if g(G) ? 16 and Δ(G) ? 3. For series-parallel graphs G, we have a′(G) ? Δ(G) + 1.
基金
supported by National Natural Science Foundation of China (Grant No. 10871119)
NaturalScience Foundation of Shandong Province (Grant No. Y2008A20).
