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

张埂

doi:10.13951/j.cnki.37-1213/n.2013.04.003

烟台大学学报（自然科学与工程版） ›› 2013, Vol. 26 ›› Issue (4) : 243 -245+249. DOI: 10.13951/j.cnki.37-1213/n.2013.04.003

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

张埂

作者信息 +

Author information +

文章历史 +

摘要

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.