Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

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 (3 k +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 .