Author
Norin, S
Scott, A
Seymour, P
Wood, D
Journal title
Combinatorica
DOI
10.1007/s00493-019-3848-z
Issue
6
Volume
39
Last updated
2023-12-19T10:56:20.33+00:00
Page
1387-1412
Abstract
The clustered chromatic number of a class of graphs is the minimum integer k such that for some integer c every graph in the class is k-colourable with monochromatic components of size at most c. We prove that for every graph H, the clustered chromatic number of the class of H-minor-free graphs is tied to the tree-depth of H. In particular, if H is connected with tree-depth t, then every H-minor-free graph is (2t+1–4)-colourable with monochromatic components of size at most c(H). This provides the first evidence for a conjecture of Ossona de Mendez, Oum and Wood (2016) about defective colouring of H-minor-free graphs. If t = 3, then we prove that 4 colours suffie, which is best possible. We also determine those minor-closed graph classes with clustered chromatic number 2. Finally, we develop a conjecture for the clustered chromatic number of an arbitrary minor-closed class.
Symplectic ID
974344
Favourite
Off
Publication type
Journal Article
Publication date
28 Oct 2019
Please contact us with feedback and comments about this page. Created on 18 Feb 2019 - 16:23.