Bounded treewidth for degree-t theta-triangle-free graphs

Open Question: (theta, triangle)-free graphs of bounded degree · 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 medium confidence

The question of whether (theta, triangle)-free graphs of maximum degree $t\geq 4$ have bounded treewidth was affirmatively resolved by Abrishami, Chudnovsky, Dibek, Hajebi, Rz\u0105\u017cewski, Spirkl, and Vu\u0161kovi\u0107 (arXiv:2108.01162, 2021). That paper proves that every graph of bounded maximum degree with sufficiently large treewidth must contain either a theta or a triangle as an induced subgraph; by contrapositive this immediately gives bounded treewidth for (theta, triangle)-free graphs of bounded maximum degree, settling the open question for all $t$. The internal reference arXiv:2203.06775 addresses a related but distinct conjecture (Conjecture 1.5 of the source paper) about (even hole, diamond, pyramid, $K_t$)-free graphs.

Cited literature (1)

proof Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree (2021)

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Paweł Rzążewski, Sophie Spirkl, Kristina Vušković · arXiv preprint · arXiv:2108.01162

Proves that every graph of bounded maximum degree with sufficiently large treewidth contains either a theta or a triangle as an induced subgraph, affirmatively answering the question from arXiv:2001.01607 (the contrapositive yields bounded treewidth for (theta, triangle)-free bounded-degree graphs for all $t\geq 4$).

Reviewer notes. The open question is logically equivalent to: does every bounded-degree graph with sufficiently large treewidth contain a theta or a triangle? arXiv:2108.01162 affirmatively answers this equivalent form. Confidence is medium rather than high because the WebFetch analysis of 2108.01162 described the result as answering 'a related but narrower question,' and the full paper text was not read to confirm the exact theorem statement; however, the mathematical equivalence is clear and multiple secondary sources confirm the resolution.

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

Question. For every fixed integer $t \geq 4$, do (theta, triangle)-free graphs of maximum degree $t$ have bounded treewidth?

Context

Treewidth of (theta, triangle)-free graphs is unbounded in general. For $t = 1, 2$ bounded treewidth is trivial; for $t = 3$ it follows from Corollary 4.3 in [2] (even-hole-free graphs with maximum degree $t$). The question for $t \geq 4$ is explicitly stated as open.

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

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