最大度是5的可平面图的边染色

华东师范大学学报(自然科学版) ›› 2011, Vol. 2011 ›› Issue (2): 32-38.

最大度是5的可平面图的边染色

倪伟平

枣庄学院数学与信息科学系, 山东枣庄 277160

收稿日期:2009-11-01 修回日期:2010-02-01 出版日期:2011-03-25 发布日期:2011-03-25
通讯作者: 倪伟平

Edge colorings of planar graphs with maximum degree five

NI Wei-ping

Department of Mathematics and Information Science, aozhuang University，Zaozhuang Shandong 277160, China

Received:2009-11-01 Revised:2010-02-01 Online:2011-03-25 Published:2011-03-25
Contact: NI Wei-ping

摘要/Abstract

摘要： 运用Discharge方法及临界图的一些重要性质证明了: 大度是5且任意一个3-圈与任意一个4-圈不相邻接, 或任意一个3-圈与任意一个5-圈不相邻接的可平面图是第一类图. 从而给出了最大度是5的可平面图是第一类图的2个充分条件.

关键词: 平面图, 边染色, 最大度, 圈, 平面图, 边染色, 最大度, 圈

Abstract: By applying a discharging method and using some theorems of critical graphs, we proved that every planar graph G with Δ=5 is of class 1, if any 3-cycle is not adjacent to any 4-cycle or to any 5-cycle in G. Therefore, we concluded two sufficient conditions for planar graph G to be Class 1.

Key words: edge coloring, maximum degree, cycle, planar graph, edge coloring, maximum degree, cycle

中图分类号:

O157.5

倪伟平. 最大度是5的可平面图的边染色[J]. 华东师范大学学报(自然科学版), 2011, 2011(2): 32-38.

NI Wei-ping. Edge colorings of planar graphs with maximum degree five[J]. Journal of East China Normal University(Natural Sc, 2011, 2011(2): 32-38.

[1]	李静云, 任韩. 关于Hamilton图的新的圈结构定理[J]. 华东师范大学学报（自然科学版）, 2020, 2020(4): 45-50.
[2]	陈晓峰, 王艺桥. 最大度为7的哈林图的L(2,1)-标号[J]. 华东师范大学学报(自然科学版), 2019, 2019(1): 39-47,57.
[3]	刘志, 刘辉平, 赵大鹏, 王晓玲. 基于移动轨迹数据的商圈消费者规模分析[J]. 华东师范大学学报(自然科学版), 2017, (4): 97-113,138.
[4]	苏静; 马飞; 姚兵; . 探索 2-边连通图的等价定义[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 19-25.
[5]	齐林明, 李金波, 李卫奇. 平面图的3-hued 染色[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 32-37.
[6]	王永强; 任韩. Halin 图的消圈数及点染色问题的研究[J]. 华东师范大学学报(自然科学版), 2016, 2016(6): 65-70.
[7]	许洋. 非负特征图的列表不完全染色的研究(英)[J]. 华东师范大学学报(自然科学版), 2016, 2016(2): 51-55.
[8]	何常香, 刘伟龙. 2n阶(n-2)-正则二部图的最小基本圈基[J]. 华东师范大学学报(自然科学版), 2016, 2016(2): 56-61.
[9]	牛爱红, 王国平, 秦正新, 牟善志. 具有最大谱半径的二部图的刻画(英)[J]. 华东师范大学学报(自然科学版), 2016, 2016(1): 96-101.
[10]	黄小佳, 陈祥恩, 王治文. 当35 ≤ d ≤ 55时圈的d-强全染色[J]. 华东师范大学学报(自然科学版), 2015, 2015(6): 30-35.
[11]	齐林明, 苗连英, 李卫奇. 关于边染色临界图的独立数[J]. 华东师范大学学报(自然科学版), 2015, 2015(1): 114-119.
[12]	蔡改香, 余桂东, 邢抱花. 具有k个悬挂点的n阶单圈图的Harary指数(英)[J]. 华东师范大学学报(自然科学版), 2015, 2015(1): 120-125.
[13]	李丹, 王国平. 给定权集的赋权双圈图的谱半径[J]. 华东师范大学学报(自然科学版), 2014, 2014(4): 39-42.
[14]	宋文耀, 苗连英, 张淑洁. 不含3-圈的1-平面图的列表边染色与列表全染色[J]. 华东师范大学学报(自然科学版), 2014, 2014(3): 40-44.
[15]	杨芳, 王治文, 陈祥恩, 马春燕. 完全图和星的合成的点可区别正常边染色[J]. 华东师范大学学报(自然科学版), 2013, 2013(5): 136-143.