4/7 clustering exponent tight for strong products

Conjecture 8 · 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 open high confidence

Conjecture 8 asks whether the O(|V(H_1 \boxtimes H_2)|^{4/7}) upper bound proved in the paper for 3-colourings of strong products of bounded-treewidth graphs is asymptotically tight; the paper's own lower bound reaches only \Omega(|V(H_1 \boxtimes H_2)|^{1/2}), leaving a gap between exponents 1/2 and 4/7. The source paper was published in The Electronic Journal of Combinatorics (Volume 32, Issue 3, 2025, DOI 10.37236/13247). No follow-up work closing this gap was found in the indexed literature.

Reviewer notes. No follow-up found. The source paper was published as ELJC Volume 32, Issue 3 (2025), DOI 10.37236/13247. The conjecture claims the 4/7 exponent in the 3-colouring upper bound is tight; the best lower bound established in the paper is 1/2, so the gap [1/2, 4/7] remains open.

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

Conjecture. There exists a positive integer $t$ such that for infinitely many graphs $H_1, H_2$ with treewidth $t$, every $3$-colouring of $H_1 \boxtimes H_2$ has clustering $\Omega(|V(H_1 \boxtimes H_2)|^{4/7})$.

Context

Theorem 3 gives an upper bound of $O(|V(H_1 \boxtimes H_2)|^{4/7})$ for 3-colourings of products of two bounded-treewidth graphs with no degree restriction, but only a lower bound of $\Omega(|V(H_1 \boxtimes H_2)|^{1/2})$ is proved. The authors conjecture the $4/7$ exponent in the upper bound is asymptotically tight.

Also stated in

Clustered Colouring of Graph Products (2024-07-31)

Notes. PDF source — exponent written inline; 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