A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V1and V0so that in G[V1] every vertex has degree at most 1, while G[V0] is edgeless. We prove that every graph with maximum average degree at most 12/5 is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to 12/5 which are not (1, 0)-colorable. In fact, we prove a stronger result by establishing the best possible sufficient condition for the (1, 0)-colorability of a graph G in terms of the minimum, Ms(G), of 6|V (A)| − 5|E(A)| over all subgraphs A of G. Namely, every graph G with Ms(G) ≥ −2 is proved to be (1, 0)-colorable, and we construct an infinite series of non-(1, 0)-colorable graphs G with Ms(G) = −3.
- Planar graphs
ASJC Scopus subject areas