Clustered Colouring of Graph Products
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929444302618624 |
|---|---|
| author | Campbell, Rutger Gollin, J. Pascal Hendrey, Kevin Lesgourgues, Thomas Mohar, Bojan Tamitegama, Youri Tan, Jane Wood, David R. |
| author_facet | Campbell, Rutger Gollin, J. Pascal Hendrey, Kevin Lesgourgues, Thomas Mohar, Bojan Tamitegama, Youri Tan, Jane Wood, David R. |
| contents | 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 $Θ(n^{2/3})$ is best possible, even if one of the graphs is a path. However, if both graphs have bounded degree, then clustering $Θ(n^{1/2})$ is best possible. With three colours, if one of the graphs has bounded degree, then we show that clustering $Θ(n^{3/7})$ is best possible. However, if neither graph has bounded degree, then clustering $Ω(n^{1/2})$ is necessary. More general bounds for any given number of colours are also presented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_21360 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Clustered Colouring of Graph Products Campbell, Rutger Gollin, J. Pascal Hendrey, Kevin Lesgourgues, Thomas Mohar, Bojan Tamitegama, Youri Tan, Jane Wood, David R. Combinatorics 05C15 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 $Θ(n^{2/3})$ is best possible, even if one of the graphs is a path. However, if both graphs have bounded degree, then clustering $Θ(n^{1/2})$ is best possible. With three colours, if one of the graphs has bounded degree, then we show that clustering $Θ(n^{3/7})$ is best possible. However, if neither graph has bounded degree, then clustering $Ω(n^{1/2})$ is necessary. More general bounds for any given number of colours are also presented. |
| title | Clustered Colouring of Graph Products |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2407.21360 |