Defective and Clustered Colouring of Graphs with Given Girth
The defective chromatic number of a graph class $\mathcal{G}$ is the minimum integer $k$ such that for some integer $d$, every graph in $\mathcal{G}$ is $k$-colourable such that each monochromatic component has maximum degree at most $d$. Similarly, the clustered chromatic number of a graph class $\mathcal{G}$ is the minimum integer $k$ such that for some integer $c$, every graph in $\mathcal{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 $K_p$ subgraph.
Authors
- David R. Wood (ORCID: https://orcid.org/0000-0001-8866-3041)
- Marcin Briański (ORCID: https://orcid.org/0000-0002-1695-0188)
- Robert Hickingbotham (ORCID: https://orcid.org/0009-0007-1817-8295)
Institutions
- Jagiellonian University (PL)
- Université Libre de Bruxelles (BE)
- Australian Regenerative Medicine Institute (AU)
- Monash University (AU)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2026-07-17
- DOI
- https://doi.org/10.37236/14855
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Australian Government
- Natural Sciences and Engineering Research Council of Canada