平面图的非正常染色*

张传妮, 王应前

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

平面图的非正常染色*

张传妮, 王应前

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

研究了特殊平面图的非正常染色问题.应用经典的权转移方法,证明了4-圈不与3-,4-圈相邻且不含7-圈的平面图是(1,1,0)-可染的.这一结果进一步拓展了平面图的非正常可染的充分条件.

平面图;圈;权转移;非正常染色

0 引 言

自从四色猜想成为四色定理[1-2](每个平面图是4色可染的)之后,Steinberg猜想[3](每个既没有4-圈又没有5-圈的平面图是3色可染的)便成为图染色理论中的一个焦点.为解决这一具极强挑战性的猜想,许多学者[4-6]作出了诸多努力,并在多方面推广了图的经典染色.图的非正常染色(或缺陷染色)便是推广之一.更准确地说,设d1,d2,…,dk是k个非负整数,G=(V,E)是一个图,若可以用k个色,譬如,c1,c2,…,ck,去染G的顶点,使得每个染色ci的顶点至多有di个邻点染有同样的色(i=1,2,…,k),则称G是非正常(d1,d2,…,dk)-可染的,简称为(d1,d2,…,dk)-可染的.运用这一术语,四色定理可改述为“每个平面图是(0,0,0,0)-可染的”,Steinberg猜想可改述为“每个既没有4-圈又没有5-圈的平面图是(0,0,0)-可染的”.图的非正常染色已得到广泛研究,并已得到许多有趣的结果.例如:

每个平面图是(2,2,2)-可染的[7];

每个既不含5-圈又不含相邻三角形的平面图是(1,1,1)-可染的[8].

从非正常染色角度研究Steinberg猜想所取得的最好结果可总结为下面的定理:

定理1 每个既没有4-圈又没有5-圈的平面图是:

1)(列表)(1,1,1)-可染的[4];

2)(3,0,0)-可染的[5];

3)(1,1,0)-可染的[9-10];

4)(2,0,0)-可染的[6].

由于Vincent Cohen-Addad等[11]最近证明了Steinberg猜想……