Defective and Clustered Colouring of Graphs with Given Girth
The Electronic Journal of Combinatorics · 17.07.2026 · 33 (3)
DOI: 10.37236/14855 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 17.07.2026. Verfasst von Marcin Briański und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Briański, M., Hickingbotham, R., & Wood, D. (2026). Defective and Clustered Colouring of Graphs with Given Girth. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/14855
Vancouver
Briański M, Hickingbotham R, Wood D. Defective and Clustered Colouring of Graphs with Given Girth. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/14855
BibTeX
@article{Briaski2026,
author = {Briański, Marcin and Hickingbotham, Robert and Wood, David},
title = {Defective and Clustered Colouring of Graphs with Given Girth},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {3},
doi = {10.37236/14855}
}
EUVIMED