I,F-Partitions of Graphs

Problem and Results Summary

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.

Research Papers

A. Brandt, M. Ferrara, M. Kumbhat, S. Loeb, D. Stolee, M. Yancey,
I,F-Partitions of sparse graphs.

Web Version

Web Version

Support

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.

Related Work

Y. Bu, D. Cranston, M. Montassier, A. Raspaud, and W. Wang.
Star coloring of sparse graphs.
*Journal of Graph Theory*, 62(3):201-219, 2009.

Official Version

Official Version