I, F-partitions of sparse graphs. (October 2016)

• Record Type: Journal Article
• Authors: Brandt, Axel; Ferrara, Michael; Kumbhat, Mohit; Loeb, Sarah; Stolee, Derrick; Yancey, Matthew
• Is Part Of: European journal of combinatorics. Volume 57(2016:Oct.)
• Page Start: 1
• Page End: 12
• Publication Date: 2016-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.03.003
• Languages: English
• ISSNs: 0195-6698

Abstract

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).