Vertex Partitions into an Independent Set and a Forest with Each Component Small

Source abstract

For each integer $k\ge 2$, we determine a sharp bound on ${mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$, where $I$ is an independent set and $G[F_k]$ is a forest in which each component has at most $k$ vertices. For each $k$ we construct an infinite family of examples showing our result is the best possible. Our results imply that every planar graph $G$ of girth at least 9 (resp., 8, 7) has a partition of $V(G)$ into an independent set $I$ and a set $F$ such that $G[F]$ is a forest with each component of order at most 3 (resp., 4, 6). Hendrey, Norin, and Wood asked for the largest function $g(a,b)$ such that if ${mad}(G)<g(a,b)$, then $V(G)$ has a partition into sets $A$ and $B$ such that ${mad}(G[A])<a$ and ${mad}(G[B])<b$. They specifically asked for the value of $g(1,b)$, i.e., the case when $A$ is an independent set. Previously, the only values known were $g(1,4/3)$ and $g(1,2)$. We find $g(1,b)$ whenever $4/3< b<2$.