EUVIMEDAtrasti EUVIMED
Crossref

Defective and Clustered Colouring of Graphs with Given Girth

Marcin Briański, Robert Hickingbotham, David Wood

The Electronic Journal of Combinatorics · 2026-07-17 · 33 (3)

DOI: 10.37236/14855 ↗

At a glance

Journal article in The Electronic Journal of Combinatorics, published online on 2026-07-17. Written by Marcin Briański and 2 co-authors.

SantraukaBibliografiniai duomenysCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →