Planar graphs without cycles of length from 4 to 6 are(1,0,0)-colorable
Ying Wang · Scientia Sinica Mathematica · 2013
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.