Abstract :
A graph G is called improperly ( d 1 , d 2 , … , d k ) -colorable, or simply ( d 1 , d 2 , … , d k ) -colorable, if the vertex set of G can be partitioned into subsets V 1 , V 2 , … , V k such that the graph G [ V i ] induced by V i has maximum degree at most d i for 1 ≤ i ≤ k . In 1976, Steinberg raised the following conjecture: every planar graph without 4- and 5-cycles is ( 0 , 0 , 0 ) -colorable. Up to now, this challenge conjecture is still open. In this paper, we prove that every planar graph without cycles of length 4 and 6 is ( 1 , 1 , 0 ) -colorable.
