平面图的 3-染色问题研究

华东师范大学学报(自然科学版) ›› 2007, Vol. 2007 ›› Issue (5): 85-88.

平面图的 3-染色问题研究

张雪媛, 陈藏, 苗连英

中国矿业大学理学院, 江苏徐州 221008

收稿日期:2006-07-29 修回日期:2007-01-25 出版日期:2007-09-25 发布日期:2007-09-25
通讯作者: 张雪媛

On the 3-Colorable Planar Graph(Chinese)

ZHANG Xue-yuan, CHEN Cang, MIAO Lian-ying

College of Science, China University of Mining andTechnology, Xuzhou Jiangsu 221008, China

Received:2006-07-29 Revised:2007-01-25 Online:2007-09-25 Published:2007-09-25
Contact: ZHANG Xue-yuan

摘要/Abstract

摘要： 研究了 3-可染色平面图的结构特征, 利用 discharging 方法证明了不含 4 圈和 5 圈且三角形间的距离至少是 2 的平面图是 3-可染色的.

关键词: 平面图, 3-染色, discharging 方法 , 平面图, 3-染色, discharging 方法

Abstract: By using the discharging method, it was proved that every
planar graph is 3-colorable, provided that it has not any 4-,
5-cycles, and the distance between any two triangles is at least 2.

Key words: 3-coloring, discharging method, planar graph, 3-coloring, discharging method

中图分类号:

O157.5

张雪媛;陈藏;苗连英. 平面图的 3-染色问题研究[J]. 华东师范大学学报(自然科学版), 2007, 2007(5): 85-88.

ZHANG Xue-yuan;CHEN Cang;MIAO Lian-ying. On the 3-Colorable Planar Graph(Chinese)[J]. Journal of East China Normal University(Natural Sc, 2007, 2007(5): 85-88.

[1]	齐林明, 李金波, 李卫奇. 平面图的3-hued 染色[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 32-37.
[2]	宋文耀, 苗连英, 张淑洁. 不含3-圈的1-平面图的列表边染色与列表全染色[J]. 华东师范大学学报(自然科学版), 2014, 2014(3): 40-44.
[3]	倪伟平. 最大度是5的可平面图的边染色[J]. 华东师范大学学报(自然科学版), 2011, 2011(2): 32-38.
[4]	倪伟平. 最大度是6不含相邻k-圈的可平面图的边染色[J]. 华东师范大学学报(自然科学版), 2010, 2010(5): 20-26.
[5]	倪伟平. 最大度是4的可平面图是第一类图的充分条件[J]. 华东师范大学学报(自然科学版), 2010, 2010(3): 85-91.
[6]	卢俊杰;任韩. 带限制条件的两个平面图同时嵌入的交叉数[J]. 华东师范大学学报(自然科学版), 2009, 2009(1): 7-12.
[7]	徐梅;任韩党英. 环面上外可平面图的最小圈基[J]. 华东师范大学学报(自然科学版), 2006, 2006(5): 72-75.
[8]	徐梅任韩党英. 环面上外可平面图的最小圈基[J]. 华东师范大学学报(自然科学版), 2006, 2006(5): 72-75.