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

Status partial medium confidence

The conjecture asks whether (even hole, $K_4$, diamond)-free graphs have bounded treewidth or cliquewidth. Abrishami, Chudnovsky, Hajebi, and Spirkl (arXiv:2203.06775, 2022) proved a partial result: for every $t > 0$, every (even hole, diamond, pyramid, $K_t$)-free graph has bounded treewidth — a special case of the conjecture that additionally requires pyramid-free graphs. Search results indicate that a structure theorem (every even-hole-free graph of sufficiently large treewidth contains $K_4$ or a diamond as an induced subgraph) was subsequently proved, which would directly resolve the conjecture, but the specific paper establishing this result could not be verified within the search budget.

Cited literature (1)

• partial Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs (2022)
  Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · Electronic Journal of Combinatorics · arXiv:2203.06775

  Proves that for every $t > 0$ there exists $d_t \geq 0$ such that every (even hole, diamond, pyramid, $K_t$)-free graph has treewidth at most $d_t$; this is a special case of the conjecture with the additional requirement of pyramid-free.

Reviewer notes. The partial result in arXiv:2203.06775 proves bounded treewidth for the subclass that additionally excludes pyramids, explicitly identified as a special case of the conjecture. Search results strongly suggest a structure theorem — that every even-hole-free graph of large treewidth must contain $K_4$ or a diamond as an induced subgraph — was subsequently proved (likely in arXiv:2309.04390, 'Induced subgraphs and tree decompositions XI'), which would directly resolve the conjecture; this paper could not be verified within the 5-call budget. Status therefore set to partial rather than solved.

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