Graph-theory open problems

Linear-growth graphs as tree boxtimes clique subgraphs

Conjecture 14 · arXiv:2210.13720

arXiv Conjecture high confidence— first stated 2022-10-25
Authors: Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, David R. Wood

Status open high confidence

Conjecture 14 from arXiv:2210.13720 proposes that every graph with growth at most cr is a subgraph of T \boxtimes K_{g(c)} for some tree T with linear growth, giving a tight characterisation of linear-growth graphs via tree products. The source paper (Theorem 13) establishes the product structure but only with a tree T that may have exponential growth; the conjecture asks that T itself be constrained to linear growth. No follow-up paper resolving the conjecture was found in a targeted web search covering publications through 2026.

Reviewer notes. No follow-up found. Related paper arXiv:2206.02395 ('Product Structure of Graph Classes with Bounded Treewidth') predates 2210.13720 and does not address Conjecture 14. arXiv:2410.19295 ('Treewidth, Hadwiger Number, and Induced Minors', 2024) by overlapping authors focuses on Hadwiger number and does not address linear growth or this conjecture. The conjecture is open with high confidence.

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

Conjecture. There exist functions $g : \mathbb{R} \to \mathbb{N}$ and $h : \mathbb{R} \to \mathbb{R}$ such that for any $c > 1$, every graph $G$ with growth $f_G(r) \leq cr$ is isomorphic to a subgraph of $T \boxtimes K_{g(c)}$ for some tree $T$ with growth $f_T(r) \leq h(c)r$.

Context

Theorem 13 shows that every graph $G$ with growth $f_G(r) \leq cr$ is a subgraph of $T \boxtimes K_{\lfloor 882c^3 \rfloor}$ for some tree $T$, but the tree $T$ itself may have exponential growth. Conjecture 14 proposes a rough characterisation of graphs of linear growth: if true, every subgraph $H$ of $T \boxtimes K_{g(c)}$ has growth $f_H(r) \leq g(c)h(c)r \in O(r)$, making the characterisation tight.

Also stated in

Source paper

Graphs of Linear Growth have Bounded Treewidth
Rutger Campbell, Marc Distel, J. Pascal Gollin, Daniel J. Harvey, Kevin Hendrey, Robert Hickingbotham, Bojan Mohar, David R. Wood · 2022-10-25
https://arxiv.org/abs/2210.13720 PDF source