Geodesic
Clustered colouring of graph products
Rutger Campbell1 ; J. Pascal Gollin2 ; Kevin Hendrey3 ; Thomas Lesgourgues4 ; Bojan Mohar5 ; Youri Tamitegama6 ; Jane Tan6 ; David R. Wood7
1Discrete Mathematics Group, Institute for Basic Science (IBS)
2FAMNIT, University of Primorska, Koper
3School of Mathematics, Monash University, Melbourne, Australia
4University of Waterloo
5Department of Mathematics, Simon Fraser University
6Mathematical Institute, University of Oxford
7School of Mathematics, Monash University
The electronic journal of combinatorics, Tome 32 (2025) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A colouring of a graph $G$ has clustering $k$ if the maximum number of vertices in a monochromatic component equals $k$. Motivated by recent results showing that many natural graph classes are subgraphs of the strong product of a graph with bounded treewidth and a path, this paper studies clustered colouring of strong products of two bounded treewidth graphs, where none, one, or both graphs have bounded degree. For example, in the case of two colours, if $n$ is the number of vertices in the product, then we show that clustering $\Theta(n^{2/3})$ is best possible, even if one of the graphs is a path. However, if both graphs have bounded degree, then clustering $\Theta(n^{1/2})$ is best possible. With three colours, if one of the graphs has bounded degree, then we show that clustering $\Theta(n^{3/7})$ is best possible. However, if neither graph has bounded degree, then clustering $\Omega(n^{1/2})$ is necessary. More general bounds for any given number of colours are also presented.
DOI : 10.37236/13247
Classification : 05C15, 05C76
Mots-clés : clustered colouring, graph products

Rutger Campbell  1   ; J. Pascal Gollin  2   ; Kevin Hendrey  3   ; Thomas Lesgourgues  4   ; Bojan Mohar  5   ; Youri Tamitegama  6   ; Jane Tan  6   ; David R. Wood  7

1 Discrete Mathematics Group, Institute for Basic Science (IBS)
2 FAMNIT, University of Primorska, Koper
3 School of Mathematics, Monash University, Melbourne, Australia
4 University of Waterloo
5 Department of Mathematics, Simon Fraser University
6 Mathematical Institute, University of Oxford
7 School of Mathematics, Monash University 
@article{10_37236_13247,
     author = {Rutger Campbell and J. Pascal Gollin and Kevin Hendrey and Thomas Lesgourgues and Bojan Mohar and Youri Tamitegama and Jane Tan and David R. Wood},
     title = {Clustered colouring of graph products},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {3},
     doi = {10.37236/13247},
     zbl = {8097643},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13247/}
}
TY  - JOUR
AU  - Rutger Campbell
AU  - J. Pascal Gollin
AU  - Kevin Hendrey
AU  - Thomas Lesgourgues
AU  - Bojan Mohar
AU  - Youri Tamitegama
AU  - Jane Tan
AU  - David R. Wood
TI  - Clustered colouring of graph products
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13247/
DO  - 10.37236/13247
ID  - 10_37236_13247
ER  - 
%0 Journal Article
%A Rutger Campbell
%A J. Pascal Gollin
%A Kevin Hendrey
%A Thomas Lesgourgues
%A Bojan Mohar
%A Youri Tamitegama
%A Jane Tan
%A David R. Wood
%T Clustered colouring of graph products
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/13247/
%R 10.37236/13247
%F 10_37236_13247
Rutger Campbell; J. Pascal Gollin; Kevin Hendrey; Thomas Lesgourgues; Bojan Mohar; Youri Tamitegama; Jane Tan; David R. Wood. Clustered colouring of graph products. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/13247

Cité par Sources :