VERTEX PARTITIONS INTO AN INDEPENDENT SET AND A FOREST WITH EACH COMPONENT SMALL

For each integer k >= 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.

Automated summary

In this paper, a sharp bound on mad(G) for integer k >= 2 is determined, and a method of partitioning V(G) into sets I and F-k is proposed. The results show that for planar graphs of girth at least 9 (resp., 8, 7), there exists a partition of V(G) such that G[F] is a forest with each component of order at most 3 (resp., 4, 6). The study also addresses the question posed by Hendrey, Norin, and Wood regarding the function g(a, b) and provides solutions for g(1, b) when 4/3 < b < 2.