Tight clustering bound in treewidth-path strong product

Conjecture 7 · arXiv:2407.21360

arXiv Conjecture medium confidence— first stated 2024-07-31

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

Status partial high confidence

Conjecture 7 asserts that for every fixed integer c≥2 the optimal clustering exponent c/(c²−c+1) for c-colourings of H⊠P (with H of fixed treewidth and P a path) is achieved by a matching lower bound. The source paper itself establishes this lower bound for c=2 (Lemma 15, exponent 2/3) and c=3 (Theorem 2, exponent 3/7), confirming the conjecture for those two cases. For c≥4 only a weaker lower bound is known and the conjecture remains open. No follow-up paper resolving the general case was found in a search of arXiv and journal literature through May 2026.

Reviewer notes. The c=2 and c=3 cases of Conjecture 7 are proved within the source paper (arXiv:2407.21360), which was subsequently published in the Electronic Journal of Combinatorics (accepted June 2025, published July 2025) as v32i3p15. For c≥4 the paper provides only the upper bound O(n^{c/(c²−c+1)}) and a weaker lower bound Ω(n^{1/(c−2/3)}); the conjecture that the tight exponent c/(c²−c+1) is achievable with a path construction remains open. No post-2024 follow-up paper addressing the general case was located.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. For any fixed integer $c \geq 2$, there exists an integer $t$ such that for infinitely many graphs $H$ with treewidth $t$ and paths $P$, every $c$-colouring of $H \boxtimes P$ has clustering $\Omega(|V(H \boxtimes P)|^{c/(c^2-c+1)})$.

Context

The upper bound in Theorem 4 gives that $H_1 \boxtimes H_2$ is $c$-colourable with clustering $O(|V(H_1 \boxtimes H_2)|^{c/(c^2-c+1)})$ when one graph has bounded degree. The authors believe this upper bound is asymptotically tight, and furthermore conjecture that there exists a matching construction where the bounded-degree graph is a path.

Notes. PDF source — exponents in the clustering bound appear inline without superscript formatting; LaTeX reconstructed from context.

Source paper

Clustered Colouring of Graph Products
Rutger Campbell, J. Pascal Gollin, Kevin Hendrey, Thomas Lesgourgues, Bojan Mohar, Youri Tamitegama, Jane Tan, David R. Wood · 2024-07-31
https://arxiv.org/abs/2407.21360 PDF source