Acyclic edge coloring of planar graphs with large girth

作者：Yu Dongxiao; Hou Jianfeng; Liu Guizhen^*; Liu Bin; Xu Lan

来源：Theoretical Computer Science, 2009, 410(47-49): 5196-5200.

DOI：10.1016/j.tcs.2009.08.015

• Acyclic coloring
• Planar graph
• Girth

Acyclic coloring problem is a specialized problem that arises in the efficient computation of Hessians. 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 chi(a)'(G) of G is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that chi(a)'(G) <= Delta(G) + 2. In this paper, we consider the sufficient conditions for the planar graphs satisfying chi(a)'(G) <= Delta(G) + 1 and chi(a)'(G) = Delta(G).

• 出版日期2009-11-6
• 单位昌吉学院; 山东大学