Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
Oleg Veniaminovich Borodin, Anna O. Ivanova, Mickaël Montassier, Pascal Ochem, André Raspaud · Journal of Graph Theory · 2009
Abstract A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V1 and V2 such that in G[V1] every vertex has degree at most k, while G[V2] 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. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010