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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Defective and Clustered Colouring of Graphs with Given Girth

David R. Wood, Marcin Briański, Robert Hickingbotham
The Electronic Journal of Combinatorics
Graph Labeling and Dimension Problems
article

Defective and Clustered Colouring of Graphs with Given Girth

David R. Wood, Marcin Briański, Robert Hickingbotham
article en

Abstract

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.

The Electronic Journal of CombinatoricsVol. 33(3)
Jagiellonian University (PL), Université Libre de Bruxelles (BE), Australian Regenerative Medicine Institute (AU), Monash University (AU)
Australian Government, Natural Sciences and Engineering Research Council of Canada
Openalex Percentile: Top 99%
Graph Labeling and Dimension Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.