A POLYNOMIAL-TIME ALGORITHM FOR EDGE COLORING A PLANAR GRAPH WITH NO ADJACENT SHORT CYCLES

摘要：

　　Let G be a planar graph such that Δ  5 and any 4-cycle is not adjacent to a 3-cycle.In the paper,we prove that G is of class 1.The proof is constructive and supplies a polynomial-time algorithm to color the edges of G with Δ(G) colors.

关键词： Edge coloring planar graph cycle class 1 algorithm

作者: Ling Xue

作者单位: Dept. of Information Engineering, Taishan Polytechnic, Taian, 271000, Shandong, China

会议类型: 国际会议

会议名称: 11th International Symposium on Operations Research and its Applications(第11届运筹学及其应用国际研讨会)

会议地点: 安徽黄山

会议语种:英文

页码: 120-122

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