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

A Sufficient Conditions for a Planar Graph of Maximum Degree Six to be Class 1

下载PDF

导出

摘要对于最大度是Δ的可平面图G,如果χ'(G)=Δ,称G为第一类图;如果χ'(G)=Δ+1,称G为第二类图,χ'(G)表示G的边色数.文章运用Discharge方法证明:最大度是6且任意一个3-圈与任意一个5-圈不相邻接的简单平面图是第一类图. Let G be a planar graph of maximum degree A, G is said to be class 1 if χ＇（G）=Δ and class 2 ifχ＇（G）=Δ＋1, where X＇（G） denotes the chromatic index of G. By applying a discharging method, we proved that every simple planar graph G with A = 6 is of class 1, if G contains no any 3 - cycle adjacent to any 5 - cycle.

作者杨星星宋杨

机构地区宿州学院数学与统计学院

出处《淮北师范大学学报（自然科学版）》 CAS 2012年第3期18-23,共6页 Journal of Huaibei Normal University：Natural Sciences

基金宿州学院一般科学研究项目(2011yyb01)

关键词平面图边染色最大度圈 planar graph edge coloring maximum degree cycle

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

引文网络
相关文献

参考文献8

1VIZING V G. On an estimate of the chromatic index of a p-graph[J].Diskret Analiz,1964,(01):25-30.
2VIZING V G. Critical graphs with given chromatic class[J].Diskret Analiz,1965,(05):9-17.
3ZHANG Liming. Every planar with maximum degree 7 is of class 1[J].Graphs and Combinatorics,2000,(04):467-495.
4SANDERS D P,ZHAO Yue. Planar graphs of maximum degree seven are class 1[J].Journal of Combinatorial Theory Series B,2001,(02):201-212.
5ZHOU Guofei. A note on graphs of class 1[J].Discrete Mathematics,2003,(1-3):339-345.
6BU Yuehua,WANG Weifan. Some sufficient conditions for a planar graph of maximum degree six to be class 1[J].Discrete Mathematics,2006,(13):1440-1445.
7LI Xuechao,LUO Rong. Edge coloring of embedded graphs with large girth[J].Graphs and Combinatorics,2003,(03):393-401.
8杨星星,苗连英,宁群.最大度是6的平面图是第一类图的一个充分条件[J].徐州师范大学学报（自然科学版）,2011,29(2):17-21. 被引量：1

二级参考文献7

1Vizing V G. On an estimate of the chromatic index of a p-graph [J]. Diskret Analiz,1964,3(1) :25.
2Vizing V G. Critical graphs with given chromatic class [J]. Diskret Analiz, 1965,5(1) : 9.
3Zhang Liming. Every planar graph with tnaximum de- gree 7 is of class 1[J]. Graphs Combin, 2000, 16 (4) :467.
4Sanders D P,Zhao Yue. Planar graphs of maximum de- gree seven are class l[J]. J Combin Theo..Ser B,2001, 83(2) :201.
5Zhou Guofei. A note on graphs of class l[J]. Discrete Math,2003,262(1/2/3):339.
6Bu Yuehua, Wang Weifan. Some sufficient conditions for a planar graph of maximum degree six to be class 1 [J]. Discrete Math, 2006,306 (13) :1440.
7Li Xuechao, Luo Rong. Edge coloring of embedded graphs with large girth[J]. Graphs Combin, 2003,19 (3) :393.

1蔡建生,王光辉,闫桂英.最大度为8不含特定子图的平面图的全染色[J].应用数学学报,2013,36(2):280-292.
2丁伟,段娟娟,王徐民.最大度为5不含6-圈的可平面图的边染色[J].淮阴师范学院学报（自然科学版）,2011,10(3):201-205.
3李国竹,尹淑英.平面图的着色数[J].石家庄职业技术学院学报,2004,16(4):57-60.
4丁伟,段娟娟,王徐民.最大度为5的可平面图是第一类的充分条件[J].苏州科技学院学报（自然科学版）,2011,28(4):22-27.
5周正同,苗连英.最大度是5的可平面图是第一类的充分条件[J].山东大学学报（理学版）,2010,45(4):24-26. 被引量：3
6莫明忠.两类联图的边色数[J].洛阳师范学院学报,2013,32(2):7-10.
7卓新建.边色数为Δ的一个充分条件[J].曲阜师范大学学报（自然科学版）,1995,21(4):99-101.
8倪伟平.最大度是5的可平面图的边染色[J].安徽大学学报（自然科学版）,2010,34(3):18-23.
9张岩,苗连英,秦健.临界图性质的探讨[J].山东科学,2007,20(2):7-9.
10扈生彪.第二类图的一个充分条件[J].青海大学学报（自然科学版）,1996,14(3):42-43.

淮北师范大学学报（自然科学版）

2012年第3期

浏览历史

内容加载中请稍等...

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

参考文献8

二级参考文献7

相关作者

相关机构

相关主题

浏览历史