不含4-圈和9-圈的平面图是(2,0,0)-可染的

Planar graphs without cycles of length 4 or 9 are (2, 0, 0)-colorable

设d1,d2,...dk为尼个非负整数.若图G的顶点集V可划分成k个子集合V1,V2…,Vk,使得对于任意的i∈{1,2,...,k},由Vi导出的子图G[Vi]的最大度至多为di,则称图G是(d1,d2,...,dk)-可染的.1976年,Steinberg猜想:不含4-圈和5-圈的平面图是(0,0,0)-可染的.在Steinberg猜想的驱动下,人们证明了以下三个结论:(1)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是列表(1,1,1)-可染的;(2)对每一个i∈{5,6,7,8,9},不含4-圈和i-圈的平面图是(1,1,0)-可染的;(3)对每一个i∈{5,6,7,8},不含4-圈和i-圈的平面图是(2,0,0)-可染的.为使结论(3)更加完整,本文证明不含4-圈和9-圈的平面图是(2,0,0)-可染的.

Let d1,d2,...,dk be k non-negative integers.A graph G is(d1,d2,…,dk)-colorable,if V,the vertex set of G,can be partitioned into subsets V1,V2,…,Vk such that the graph G[Vi]induced by Vi has the maximum degree at most di for i=1,2,...,k.In 1976,Steinberg conjectured that every planar graph without cycles of length 4 or 5 is(0,0,0)-colorable.Motivated by Steinberg’s conjecture,a number of authors proved the following three conclusions:(1)for every i∈{5,6,7,8,9},every planar graph without cycles of length 4 or i is list(1,1,1)-colorable;(2)for every i∈{5,6,7,8,9},every planar graph without cycles of length 4 or i is(1,1,0)-colorable;(3)for every i∈{5,6,7,8},every planar graph without cycles of length 4 or i is(2,0,0)-colorable.To make Conclusion(3)neat as Conclusions(1)and(2),we prove that planar graphs without cycles of length 4 or 9 are(2,0,0)-colorable.