EUVIMEDEUVIMED entdecken
Crossref

Clustered Colouring of Graph Products

Rutger Campbell, J. Pascal Gollin, Kevin Hendrey, Thomas Lesgourgues, Bojan Mohar, Youri Tamitegama, Jane Tan, David R. Wood

The Electronic Journal of Combinatorics · 18.07.2025 · 32 (3)

DOI: 10.37236/13247 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 18.07.2025. Verfasst von Rutger Campbell und 7 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Campbell, R., Gollin, J. P., Hendrey, K., Lesgourgues, T., Mohar, B., Tamitegama, Y., Tan, J., & Wood, D. R. (2025). Clustered Colouring of Graph Products. The Electronic Journal of Combinatorics, 32(3). https://doi.org/10.37236/13247

Vancouver

Campbell R, Gollin JP, Hendrey K, Lesgourgues T, Mohar B, Tamitegama Y, et al. Clustered Colouring of Graph Products. The Electronic Journal of Combinatorics. 2025;32(3). doi:10.37236/13247

BibTeX
@article{Campbell2025,
  author = {Campbell, Rutger and Gollin, J. Pascal and Hendrey, Kevin and Lesgourgues, Thomas and Mohar, Bojan and Tamitegama, Youri and Tan, Jane and Wood, David R.},
  title = {Clustered Colouring of Graph Products},
  journal = {The Electronic Journal of Combinatorics},
  year = {2025},
  volume = {32},
  number = {3},
  doi = {10.37236/13247}
}
Kostenlos starten →