Bounded treewidth for (C₄, diamond, theta, prism)-free graphs

Conjecture 1.6 · arXiv:2203.06775

arXiv Conjecture high confidence— first stated 2022-10-21

Authors: Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Status open medium confidence

Conjecture 1.6 posits a constant treewidth bound $\mathrm{tw}(G) \leq c_t$ for all $G \in \mathcal{C}^*_t$ ($(C_4$, diamond, theta, prism, even wheel, $K_t)$-free graphs). No verified proof or counterexample of the full conjecture was found. The closely related Sintiari–Trotignon conjecture (Conjecture 1.5 in the source paper) on even-hole-free $K_t$-free graphs was resolved in 2024 by arXiv:2402.14211 with a logarithmic bound $c_t \log n$ shown to be asymptotically tight, which does not settle Conjecture 1.6 since $\mathcal{C}^*_t$ is a more restricted class and the conjecture asks for a constant bound. Web searches suggest possible counterexamples to related bounded-treewidth conjectures by Hajebi (a co-author) appearing in 2025, but these could not be verified within the search budget.

Cited literature (1)

partial Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number (2024)

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl · arXiv preprint · arXiv:2402.14211

Proves every $n$-vertex even-hole-free graph with no $K_t$ satisfies $\mathrm{tw}(G) \leq c_t \log n$ and shows this logarithmic bound is tight, resolving Conjecture 1.5 (Sintiari–Trotignon) but leaving Conjecture 1.6's constant bound for the more restricted class $\mathcal{C}^*_t$ open.

Reviewer notes. Conjecture 1.6 asks for a CONSTANT bound $c_t$ on $\mathrm{tw}$ for $\mathcal{C}^*_t$, which is a harder question than the logarithmic bound proved for the strictly larger even-hole-free $K_t$-free class by arXiv:2402.14211. Web searches surfaced a 2025 Journal of Graph Theory paper by Hajebi ('Chordal Graphs, Even-Hole-Free Graphs and Sparse Obstructions to Bounded Treewidth') and a mention of counterexamples to a Hajebi-attributed bounded-treewidth conjecture, but these could not be verified within the 5-call budget; confidence is set to medium rather than high for this reason.

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

Conjecture. For all $t > 0$ there exists $c_t \geq 0$ such that $\mathrm{tw}(G) \leq c_t$ for every $G \in \mathcal{C}^*_t$.

Context

Here $\mathcal{C}^*_t$ denotes the class of $(C_4, \text{diamond}, \text{theta}, \text{prism}, \text{even wheel}, K_t)$-free graphs — a relaxation of $\mathcal{C}_t$ in which pyramids are no longer excluded. The authors pose this as a slight generalization of Sintiari–Trotignon's Conjecture 1.5, noting that Theorem 1.4 (the main result of the paper) would serve as the base case if the conjecture could be proved by the same techniques.

Source paper

Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · 2022-10-21
https://arxiv.org/abs/2203.06775 PDF source