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

设d₁, d₂,..., d_k 是k个非负整数. 若图G=(V,E) 的顶点集V可剖分成k个子集V₁, V₂,..., V_k,使得对i=1, 2,..., k 由V_i 所导出的子图GV_i] 的最大度至多为d_i, 则称G是(d₁, d₂,..., d_k)-可染的. 著名的Steinberg 猜想断言, 每个既没有4-圈又没有5-圈的平面图是(0, 0, 0)-可染的. 对此猜想已经证明每个没有4 至7-圈的平面图是(0, 0, 0)-可染的, 但还没有发现有人证明每个没有4 至6-圈的平面图是(0, 0, 0)-可染的. 本文证明没有4 至6-圈的平面图是(1, 0, 0)-可染的.

Planar graphs without cycles of length from 4 to 6 are （1, O,O）-colorable

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 GVi] 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.