[1]赵春红,董伟.平面图3可着色的充分条件[J].南京师大学报(自然科学版),2011,34(03):13-18.
　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-18.
点击复制

平面图3可着色的充分条件()
分享到：

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

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

文章信息/Info

Title:
The Sufficient Conditions on 3-Colorable Plane Graphs
作者:
赵春红1; 2; 董伟1
( 1． 南京师范大学数学科学学院，江苏南京210046) ( 2． 沙洲职业工学院建筑工程系，江苏张家港215600) ( 3． 南京晓庄学院数学与信息技术学院，江苏南京211171)
Author(s):
Zhao Chunhong1; 2; Dong Wei1; 3
1.School of Mathematical Sciences,Nanjing Normal University,Nanjing 210046,China
关键词:
平面图; 圈; 着色
Keywords:
plane graph;  cycle;  coloring
分类号:
O157.5
摘要:
证明了(1)每一个不含4-6圈,也不含距离小于2的三角形对,且每个7-圈最多与一个三面相邻的平面图是3-可着色的;(2)每一个不含4-圈和5-圈,且每个6-圈或7-圈不与长度小于8的圈有公共边的平面图是3-可着色的.
Abstract:
This paper proveed the following sufficient conditions on 3-colorable plane graphs: ( 1) Let G be a plane graph with neither cycles of length from 4 to 6 nor triangles of distance less than two． Furthermore， if every 7-cycles of G is adjacent to at most one triangle， then G is 3-colorable; ( 2) Every plane graph with neither cycles of length 4，5 nor cycles of length 6 and 7 adjacent to cycles of length less than 8 is 3-colorable．

参考文献/References:

［1］ Bondy J A，Murty U S R． Graph Theory With Applications［M］． New York: Macmillan Ltd Press，1976．
［2］ Abbott H L，Zhou B． Om small faces in 4-critical graphs［J］． Ars Combin，1991，32: 203-207．
［3］ Borodin O V，Glebov A N，Raspaud A，et al． Planar graphs without cycles of length from 4 to 7 are 3-colorable［J］． J Combin Theroy Ser B，2005，93: 303-311．
［4］ Xu B． On 3-colorable plane graphs without 5-and 7-cyclesm［J］． J Combin Thery Ser B，2006，96: 958-963．

相似文献/References:

[1]鲁晓旭,许宝刚.关于平面图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.
[2]张海辉,沈邦玉.关于无6-,8-和9-圈平面图的3-选色[J].南京师大学报(自然科学版),2004,27(02):39.
　Zhang Haihui~.On 3-Choosability of Plane Graphs without 6-, 8-and 9-Cycles[J].Journal of Nanjing Normal University(Natural Science Edition),2004,27(03):39.
[3]卞秋香,孙志人.2-连通图过指定边的长圈(英文)[J].南京师大学报(自然科学版),2003,26(02):10.
　Bian Qiuxiang,Sun Zhiren.Large Cycles Passing Through a Specified Edge in 2-connected Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2003,26(03):10.
[4]倪伟平.最大度是6且不含有弦的小圈的可平面图的边染色[J].南京师大学报(自然科学版),2011,34(03):19.
　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.

备注/Memo

备注/Memo:
通讯联系人:赵春红，讲师，研究方向: 图论与组合优化． E-mail: zhaochunhong10@163． Com
更新日期/Last Update: 2011-09-15