关于平面图3-可着色的一个定理(英文)  

A Theorem on 3-Colorable Plane Graphs

作　　者：鲁晓旭[1] 许宝刚[1] 

机构地区：[1]南京师范大学数学与计算机科学学院,江苏南京210097

出　　处：《南京师大学报（自然科学版）》2006年第3期5-8,共4页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：SupportedbytheNationalNaturalScienceFoundationofChina(10371055)

摘　　要：Borod in和Raspaud提出一个猜想:任何既没有5-圈也没有相邻三角形的平面图是3-可着色.这个猜想强化了Ste inberg提出的猜想.在本文中,我们研究了没有5-,6-,9-圈并且没有相邻三角形的平面图的结构.利用这个结构,证明了这类图是3-可着色的.它加强了由Borod in及Sand-ers和Zhao的结果,并且又是对Borod in和Raspaud猜想的一个正面的支持.Borodin and Raspaud proposed a conjecture which claims that evers plane graph without 5-cireuits and adjacent triangles is 3-colorable. This strengthens a conjecture of Steinberg. In this paper, we study the structure of plane graphs without 5-, 6- and 9-circuits and adjacent triangles. As a corollary, we prove that such graphs are 3-colorable, this improves a result by Borodin, and independently by Sanders and Zhao, and also provides a positive support to Borodin and Raspaud＇s conjecture.

关 键 词：平面图 圈 着色 

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