A star k -coloring is a proper k -coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than 5 2 has an I,F-partition, which is sharp and answers a question of Cranston and West (0000). This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu etźal. (2009).
['Axel Brandt', 'Michael Ferrara', 'Mohit Kumbhat', 'Sarah Loeb', 'Derrick Stolee', 'Matthew Yancey']
I,F-partitions of sparse graphs