您的位置:首页  > 论文页面

最大度为6的平面图是第一类图的充分条件

发表时间:2010-07-15  浏览量:1698  下载量:421
全部作者: 周正同,苗连英
作者单位: 中国矿业大学理学院
摘 要: 对于最大度为Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图,χ′(G)表示G的边染色数。1965年,VIZING证明了任何一个最大度大于等于8的可平面图均是第一类图,并找到了Δ∈{2,3,4,5}的第二类可平面图,同时猜想6≤Δ≤7的平面图是第一类的。运用Discharge方法证明:最大度为6且不含7�圈的可平面图G是第一类图。
关 键 词: 图论;平面图;边染色;最大度;圈
Title: A sufficient conditions for a planar graph of maximum degree six to be class 1
Author: ZHOU Zhengtong, MIAO Lianying
Organization: School of Sciences, China University of Mining and Technology
Abstract: Let G be a planar graph of maximum degreeΔ, G is said to be class 1 if χ′(G)=Δ and class 2 if χ′(G)=Δ+1, where χ′(G)denotes the chromatic index of G. In 1965, Vizing proved that every planar graph of maximum degree at least eight is of class 1, and presented examples of planar graphs of class 2 for Δ∈{2,3,4,5}, and conjectured that the conclusion holds for the 6≤Δ≤7 case.By applying a discharg method, we proved that every simple planar graph G with Δ=6 is of class 1, if G contains no any 7�cycle�
Key words: graph theroy; planar graph; edge coloring; maximum degree; cycle
发表期数: 2010年7月第13期
引用格式: 周正同,苗连英. 最大度为6的平面图是第一类图的充分条件[J]. 中国科技论文在线精品论文,2010,3(13):1348-1354.
 
3 评论数 0
暂无评论
友情链接