Abstract:
A graph $G$ is $(1,0)$-colorable if its vertex set can be partitioned into subsets $V_1$ and $V_0$ so that in $G[V_1]$ every vertex has degree at most $1$, while $G[V_0]$ is edgeless. We prove that every graph with maximum average degree at most $\frac{12}5$ is $(1,0)$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 $\frac{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)\ge-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$.