[1]倪伟平.最大度是6且不含有弦的小圈的可平面图的边染色[J].南京师范大学学报(自然科学版),2011,34(03):19-24.
 Ni Weiping.Edge Coloring of Planar Graphs With Δ=6 Without Short Cycles Contain Chords[J].Journal of Nanjing Normal University(Natural Science Edition),2011,34(03):19-24.
点击复制

最大度是6且不含有弦的小圈的可平面图的边染色()
分享到:

《南京师范大学学报》(自然科学版)[ISSN:1001-4616/CN:32-1239/N]

卷:
第34卷
期数:
2011年03期
页码:
19-24
栏目:
数学
出版日期:
2011-09-20

文章信息/Info

Title:
Edge Coloring of Planar Graphs With Δ=6 Without Short Cycles Contain Chords
作者:
倪伟平
枣庄学院数学与统计学院,山东枣庄277160
Author(s):
Ni Weiping
School of Mathematics and Statistics,Zaozhuang University,Zaozhuang,277160,China
关键词:
平面图边染色最大度
Keywords:
planar graphedge coloringmaximum degreecycle
分类号:
O157.5
摘要:
对于最大度是Δ的可平面图G,如果χ’(G)=Δ,称G为第一类图;如果χ’(G)=Δ+1,称G为第二类图,χ’(G)表示G的边染色数.1965年,Vizing证明了任何一个Δ≥8的可平面图均是第一类图,并猜想Δ=6的可平面图也是第一类图.本文运用Discharge方法证明了最大度是6,且不含有弦的k-圈的可平面图是第一类图(4≤k≤7).
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. By applying a Discharging method,we prove that every simple planar graph G with Δ = 6 is of class 1,if G does not contain chordal-k-cycles ( 4≤k≤7) .

参考文献/References:

[1] Vizing V G. On an estimate of the chromatic index of a p-graph[J]. Diskret Analiz,1964,3 ( 1) : 25-30.
[2] Vizing V G. Critical graphs with given chromatic class[J]. Diskret Analiz,1965,5 ( 1) : 9-17.
[3] Sanders D P,Zhao Y. Planar graphs of maximum degree seven are class 1[J]. Combin Theory Ser B,2001,83( 2) : 201- 212.
[4] Zhang L. Every planar with maximum degree 7 is of class 1[J]. Graphs Combin,2000, 16( 4) : 467-495.
[5] Zhou G. A note on graphs of class 1[J]. Discrete Math,2003,263( 1 /3) : 339-345.
[6] Bu Y,Wang W. Some sufficient conditions for a planar graph of maximum degree six to be class 1[J]. Discrete Math,2006, 306( 13) : 1 440-1 445.
[7] Li X,Luo R. Edge coloring of embedded graphs with large girth[J]. Graphs Combin,2003, 19( 3) : 393-401.
[8] Wang Weifan,Chen Yongzhu. A sufficient condition for a planar graph to be class 1[J]. Theoret Computer Sci,2007,385 ( 1 /3) : 71-77.

相似文献/References:

[1]赵春红,董伟.平面图3可着色的充分条件[J].南京师范大学学报(自然科学版),2011,34(03):13.
 Zhao Chunhong,Dong Wei.The Sufficient Conditions on 3-Colorable Plane Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2011,34(03):13.
[2]鲁晓旭,许宝刚.关于平面图3-可着色的一个定理(英文)[J].南京师范大学学报(自然科学版),2006,29(03):5.
 Lu Xiaoxu,Xu Baogang.A Theorem on 3-Colorable Plane Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2006,29(03):5.

备注/Memo

备注/Memo:
基金项目:国家自然科学基金( 61075033) .通讯联系人:倪伟平,硕士,副教授,研究方向: 图论. E-mail: niweipingdd@ yahoo. com. Cn
更新日期/Last Update: 2011-09-15