2024/04/23 by Briański, Marcin, Hickingbotham, Robert, Wood, David R.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2404.14940
The defective chromatic number of a graph class G is the minimum integer k such that for some integer d, every graph in G is k-colourable such that each monochromatic component has maximum degree at most d. Similarly, the clustered chromatic number of a graph class G is the minimum integer k such that for some integer c, every graph in G is k-colourable such that each monochromatic component has at most c vertices. This paper determines or establishes bounds on the defective and clustered chromatic numbers of graphs with given girth in minor-closed classes defined by the following parameters: Hadwiger number, treewidth, pathwidth, treedepth, circumference, and feedback vertex number. One striking result is that for any integer k, for the class of triangle-free graphs with treewidth k, the defective chromatic number, clustered chromatic number and chromatic number are all equal. The same result holds for graphs with treedepth k, and generalises for graphs with no Kp subgraph.