Acyclic edge colorings of planar graphs and seriesparallel graphs
Tóm tắt
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.
Tài liệu tham khảo
Grünbaum B. Acyclic colorings of planar graphs. Israel J Math, 14: 390–408 (1973)
Alon N, Zaks A. Algorithmic aspects of acyclic edge colorings. Algorithmica, 32: 611–614 (2002)
Borodin O V. On acyclic colorings of planar graphs. Discrete Math, 25: 211–236 (1979)
Kostochka A V, Melńikov L S. Note to the paper of Gr"unbaum on acyclic colorings. Discrete Math, 14: 403–406 (1976)
Alon N, McDiarmid C J H, Reed B A. Acyclic coloring of graphs. Random Structures Algorithms, 2: 277–288 (1991)
Molloy M, Reed B. Further algorithmic aspects of the local lemma. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, May 1998, 524–529
Alon N, Sudakov B, Zaks A. Acyclic edge colorings of graphs. J Graph Theory, 37: 157–167 (2001)
Burnstein M I. Every 4-valent graph has an acyclic 5-coloring (in Russian). Soobšč Akad Nauk Gruzin SSR, 93: 21–24 (1979) (Georgian and English summaries)
van den Heuvel J, McGuinness S. Coloring the square of a planar graph. J Graph Theory, 42: 110–124 (2003)
Duffin R J. Topology of series-parallel networks. J Math Anal Appl, 10: 303–318 (1965)
Wu J, Wu Y. The entire coloring of series-parallel graphs. Acta Math Appl Sin, 21: 61–66 (2005)