平面图3色可染的一个充分条件  

A sufficient condition for a planar graph to be 3-colorable

作　　者：亢莹利[1] 王应前[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,金华321004

出　　处：《中国科学：数学》2013年第4期409-421,共13页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11271335)资助项目

摘　　要：Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的.Xu,Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3色可染的.作为这一结果的推论,没有4-,5-和7-圈的平面图是3色可染的.本文证明一个比此推论更接近Steinberg猜想的结果,设G是一个既没有4-圈又没有5-圈的平面图,若对每一个k∈{3,6,7},G都不含(k,7)-弦,则G是3色可染的,这里的(k,7)-弦是指长度为7+k2的圈的一条弦,它的两个端点将圈分成两条路,一条路的长度为6,另一条路的长度为k1.Steinberg conjectured that every planar graph with neither cycle of length 4 nor cycle of length 5 is 3-colorable. Xu, independently, Borodin et al. proved that planar graphs without adjacent triangles and without 5- and 7-cycles are 3-colorable. As a corollary of this result, planar graphs without 4-, 5- and 7-cycles are 3-colorable. In this paper, we prove a result which is closer to the Steinberg＇s conjecture than the corollary mentioned above. Let G be a planar graph without 4- and 5-cycles. G is 3-colorable if it has no （κ1 7）-chords for each κ ∈ {3, 6, 7}, where a （κ, 7）-chord is a chord of a cycle of length 7 ＋ k - 2 whose two ends divide the cycle into two paths, one of which is of length 6 and the other of length κ - 1.

关 键 词：Steinberg猜想 平面图 圈 弦 染色 

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