Acyclic Edge Colorings of Planar Graphs Without Short Cycles

摘要：

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 is the least number of colors in an acyclic edge coloring of G. In this paper, it is proved that the acyclic edge chromatic number of a planar graph G is at most △(G) + 2 if G contains no i-cycles, 4 ≤ i ≤ 8, or any two 3-cycles are not incident with a common vertex and G contains no i-cycles, i = 4 and 5.

关键词： acyclic edge coloring girth planar graph cycle

作者: Xiang-Yong Sun Jian-Liang Wu

作者单位: School of Statistics and Math., Shandong Economic University, Jinan, 250014, China School of Mathematics, Shandong University, Jinan, 250100, China

会议类型: 国际会议

会议名称: The Seventh International Symposium(ISORA08)(第七届国际效力研究及其应用学术会议)

会议地点: 云南丽江

会议语种:英文

页码: 325-329

在线出版日期: 2008-10-31（万方平台首次上网日期，不代表论文的发表时间）