I, F-partitions of sparse graphs. (October 2016) - Brandt, Axel; Ferrara, Michael; Kumbhat, Mohit; Loeb, Sarah; Stolee, Derrick; Yancey, Matthew
Abstract: 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).