Graph-theory open problems

Bounded treewidth for even-hole K₄ diamond-free graphs

Open Question: (even hole, K4, diamond)-free treewidth/cliquewidth · arXiv:2001.01607

arXiv Question medium confidence— first stated 2020-10-27
Authors: Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon

Status solved high confidence

Yes: a later theorem states that every even-hole-free graph of sufficiently large treewidth contains an induced diamond or a K4.

Cited literature (2)

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The deep later structure theorem is used as a black box, and no explicit numerical treewidth bound is extracted.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

Question. Is it true that (even hole, $K_4$, diamond)-free graphs have bounded treewidth (or cliquewidth)?

Context

The paper proves bounded treewidth for (theta, triangle, $S_{i,j,k}$)-free and (even hole, pyramid, $K_t$, $S_{i,j,k}$)-free graphs. The analogous question for graphs excluding the diamond ($K_4$ minus one edge) instead of a subdivided claw is explicitly listed as open.

Notes. PDF source — math notation reconstructed; stated in the dedicated 'Open questions' section of the paper.

Source paper

(Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 2 : bounds on treewidth
Marcin Pilipczuk, Ni Luh Dewi Sintiari, Stéphan Thomassé, Nicolas Trotignon · 2020-10-27
https://arxiv.org/abs/2001.01607 PDF source

Related conjectures

  • implied by Bounded tree-α in (even hole, diamond)-free graphs partial Hypothesis-class containment plus Ramsey. (even hole, K_4, diamond)-free graphs are in particular (even hole, diamond)-free, so the source conjecture gives a tree decomposition in which every bag B satisfies alpha(G[B]) <= a for some universal a. Since G is K_4-free, G[B] also has no clique of size 4, so by Ramsey |B| < R(4, a+1). Hence treewidth is bounded by R(4, a+1) - 2, answering the target question positively (bounded treewidth also implies bounded cliquewidth, covering the parenthetical). Direction is correct: the source statement about the larger class forces the target.
  • implied by Bounded treewidth for (C₄, diamond, theta, prism)-free graphs open Each of C_4, theta, prism, even wheel contains an even hole: C_4 is itself one; in a theta two of the three internally disjoint paths share parity and form an even induced cycle; in a prism two same-parity paths P_i, P_j plus the two triangle edges form an even hole of length l_i + l_j + 2 >= 4; in an even wheel either some sector between consecutive spokes has even length (even hole through the center) or all sectors are odd and, the number of spokes being even, the rim itself is an even hole. Hence (even hole, K_4, diamond)-free is contained in C*_4 = (C_4, diamond, theta, prism, even wheel, K_4)-free, and the t = 4 instance of the source bounds its treewidth (hence cliquewidth), answering the target. One sketch mis-phrases this as 'the t=4 case of the target', but the claimed direction source -> target is correct.

View in the relation graph — relations are AI-reviewed, not formally verified.