不包含{4,8,9}-圈的平面图是3-可染的  

ON THE 3-COLORABILITY OF PLANAR GRAPHS WITHOUT{4,8,9}-CYCLES

作　　者：方冬云[1] 

机构地区：[1]莆田学院数学与应用数学系,莆田351100

出　　处：《系统科学与数学》2012年第9期1155-1165,共11页Journal of Systems Science and Mathematical Sciences

基　　金：福建省高校服务海西项目(2008HX03);福建省教育厅科技项目(JB11172)资助课题

摘　　要：主要围绕Steinberg提出猜想:每个不包含4-圈和5-圈的平面图都是3-可染色的,对一些平面图类展开研究,提出要解决的问题:不包含{4,8,9}-圈的平面图是3-可染的.现从四个方面:不包含{4,8,9}-圈的平面图G的一些结构性质;不包含{4,8,9}-圈的平面图G中内部非分离6-圈的性质;不包含{4,8,9}-圈的平面图G不包含内部的6-面;f0不是一个6-面来证明结论,即不包含{4,8,9}-圈的平面图是3-可染的.This paper focuses on the Steinberg conjecture that every planar graph without 4 and 5-cycles is 3-colorable. The 3-colorability of some classes of planar graphs is studied. The main result of the paper is： Planar graphs without cycles of length 4, 8, 9 are 3-colorable. We introduce some structural properties and the nature of internal non-separating 6-cycle in planar grasp G without {4, 8, 9}-cycles, and then show that G has no internal 6-face and ｜f0｜≠ 6. Finally, we conclude that planar graphs without cycles of length 4, 8, 9 are 3-colorable.

关 键 词：平面图 3-可染 分离圈 

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