Abstract
We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph G admits an (I, O k)-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order at most k. We prove that every graph G with mad(G) < 5 2 admits an (I, O 3)-partition. This implies that every planar graph with girth at least 10 can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 3. We also prove that every graph G with mad(G) < 8k 3k+1 = 8 3 1 − 1 3k+1 admits an (I, O k)-partition. This implies that every planar graph with girth at least 9 can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 9.