不含3圈的平面图的无圈边染色  

Acyclic Edge Coloring of Planar Graphs without 3 Cycles

作　　者：张江[1] 张埂[2] 

机构地区：[1]西南交通大学牵引动力国家重点实验室,四川成都610031 [2]重庆大学自动化学院,重庆400030

出　　处：《贵州大学学报（自然科学版）》2013年第5期9-12,共4页Journal of Guizhou University:Natural Sciences

基　　金：中央高校基本科研业务费专项基金(LK0103)

摘　　要：图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过Δ(G)+3.One of the main subjects of coloring theory of graph is acyclic edge coloring. In 2001, Alon et al. conjectured that the acyclic chromatic number of any simple graph G is no more than △ （G） ＋ 2 , where △ （G） is the maximum degree of G. In order to prove the conjecture is true for planar graphs, in this paper, we proved that the acyclic chromatic number of planar graphs without 3 cycles is no more than △ （G） ＋ 3 with discharging method.

关 键 词：无圈边染色 无圈边色数 平面图 差值转移法 

分 类 号：O157.5[理学—数学]