A 2-independent set in a graph $G$ is a set $I \subseteq V(G)$ such that $d(u,v) \geq 2$ for all $u, v \in I$. An I,F-partition of a graph $G$ is a partition $V(G) = I \cup F$ such that $I$ is a 2-independent set and $G[F]$ is a forest.

If $G$ has an I,F-partition, then this partition can be used to create a proper 4-coloring where the union of any two color classes is a star forest; thus, the star chromatic number of $G$ is at most 4.

As part of GRWC 2015, we investigated sparsity conditions that imply $G$ has an I,F-partition. In terms of the maximum average degree, $\operatorname{Mad}(G)$, we have a sharp bound.

Theorem. Let $G$ be a graph with $\operatorname{Mad}(G) < 2 + \frac{1}{2}$. There exists an I,F-partition of $G$ and hence $\chi_s(G) \leq 4$.

In particular, planar graphs of girth at least 10 have an I,F-partition and star chromatic number at most 4.

This collaboration began as part of the 2015 Rocky Mountain/Great Plains Graduate Research Workshop in Combinatorics, supported in part by NSF Grant #1500662. Michael Ferrara was supported by Simons Collaboration Grant #206692.