没有4至6-圈的平面图是(1,0,0)-可染的  

Planar graphs without cycles of length from 4 to 6 are(1,0,0)-colorable

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

机构地区：[1]浙江师范大学数学系,金华321004

出　　处：《中国科学：数学》2013年第11期1145-1164,共20页Scientia Sinica：Mathematica

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

摘　　要：设d1,d2,...,dk是k个非负整数.若图G=(V,E)的顶点集V可剖分成k个子集V1,V2,...,Vk,使得对i=1,2,...,k由V i所导出的子图G[V i]的最大度至多为d i,则称G是(d1,d2,...,dk)-可染的.著名的Steinberg猜想断言,每个既没有4-圈又没有5-圈的平面图是(0,0,0)-可染的.对此猜想已经证明每个没有4至7-圈的平面图是(0,0,0)-可染的,但还没有发现有人证明每个没有4至6-圈的平面图是(0,0,0)-可染的.本文证明没有4至6-圈的平面图是(1,0,0)-可染的.Let d1, d2…… dk be k nonnegative integers. A graph G = （V, E） is improperly （d1,d2……, dk）- colorable, if the vertex set V of G can be partitioned into subsets V1, V2…… Vk such that the subgraph G[Vi] induced by Vi has maximum degree at most di for i = 1, 2…… k. In terms of improper colorability, the famous Steinberg Conjecture asserts that every planar graph with cycles of length neither 4 nor 5 is （0, 0, 0）-colorable. Towards this conjecture, it is known that every planar graph without cycles of length from 4 to 7 is （0, 0, 0）- colorable. However, it is unknown whether every planar graph without cycles of length from 4 to 6 is （0, 0, 0）- colorable. In this paper, we prove that planar graphs without cycles of length from 4 to 6 are （1, 0, 0）-colorable.

关 键 词：Steinberg猜想 非正常染色 坏圈 超延拓 权转移 

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