20.500.12556/RUL-175142 Clustered colouring of graph products 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. graph products colouring clustering true false true Angleški jezik Angleški jezik Članek v reviji 2025-10-17 14:47:54 2025-10-17 14:47:59 2025-12-06 04:06:29 0000-00-00 00:00:00 2025 0 0 24 str. iss. 3, article no. P3.15 Vol. 32 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-01-01 519.17 1077-8926 10.37236/13247 253497859 13247-PDF_file-55713-1-10-20250707.pdf 13247-PDF_file-55713-1-10-20250707.pdf 1 6866A1878462466D0BF09F1E85DFBC97 839d0aeeebd2a8ba3637215db62386fc95b9451acec627a438b830bb608abcfe 5800b942-ab58-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=220439 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i3p15 1 421c345b-ab57-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=220438 Fakulteta za matematiko in fiziko 0 0 0