不含三角形的平面图的无圈边染色  

Acyclic Edge Coloring of Planar Graphs without Triangles

作　　者：张埂[1] 

机构地区：[1]四川文理学院学报编辑部,四川达州635000

出　　处：《烟台大学学报（自然科学与工程版）》2013年第4期243-245,249,共4页Journal of Yantai University(Natural Science and Engineering Edition)

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

摘　　要：图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.One of the main subjects of coloring theory of graphs is the acyclic edge coloring of graphs. In 2001, Alon et al. conjectured that the acyclic chromatic number of any simple graphs G is no more than △（G） ＋2, where A（G） is the maximum degree of G. In this paper, by using discharging methods and some properties of minimal graphs, we prove that if a planar graph G is without triangles and its maximum degree is at least 6, then its acyclic chromatic number is no more than △（G） ＋3. As a result, we partly show that the conjecture is true for some spe- cial planar graphs.

关 键 词：无圈边染色 无圈边色数 平面图 三角形 

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