A graph G is (k,0)-colorable if its vertices can be partitioned into subsets V_1 and V_2 such that in G[V_1] every vertex has degree at most k, while G[V_2] is edgeless. For every integer k≥0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)-colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)-colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)-colorable for arbitrarily large k.
展开▼
