Let d 1 , d 2 , ? , d k be k nonnegative integers. A graph G = ( V , E ) is ( d 1 , d 2 , ? , d k ) -colorable, if the vertex set V of G can be partitioned into subsets V 1 , V 2 , ? , V k such that the subgraph G V i induced by V i has maximum degree at most d i for i = 1 , 2 , ? , k . Steinberg conjectured that planar graphs without cycles of length 4 or 5 are ( 0 , 0 , 0 ) -colorable. Hill et?al. showed that every planar graph without cycles of length 4 or 5 is ( 3 , 0 , 0 ) -colorable. In this paper, we show that planar graphs without cycles of length 4 or 5 are ( 2 , 0 , 0 ) -colorable. For further study in this direction, some problems and conjectures are presented.
['Ming Chen', 'Yingqian Wang', 'Peipei Liu', 'Jinghan Xu']
Planar graphs without cycles of length 4 or 5 are ( 2 , 0 , 0 ) -colorable