Induced wall in bounded-degree high tree-width graphs

Conjecture 3 · arXiv:2008.05504

arXiv Conjecture high confidence— first stated 2020-08-12

Authors: Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon

Status solved high confidence

Conjecture 3 from arXiv:2008.05504 was proved by Korhonen (arXiv:2203.13233, JCTB 2023), who showed that every graph of bounded maximum degree and sufficiently large treewidth contains a large wall or the line graph of a large wall as an induced subgraph. Prior partial progress by Abrishami, Chudnovsky, Dibek, Hajebi, and Rzążewski (arXiv:2108.01162) established the conclusion for $S_{t,t,t}$-free graphs and $(t$-theta, $t$-pyramid)-free graphs of bounded degree and large treewidth.

Cited literature (2)

partial 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 · Journal of Combinatorial Theory, Series B · arXiv:2108.01162

Proves the conjecture for $S_{t,t,t}$-free bounded-degree graphs (obtaining the line graph of a subdivision of $W_{k\times k}$ as an induced subgraph) and for $(t$-theta, $t$-pyramid)-free graphs of bounded degree and sufficiently large treewidth.
proof Grid Induced Minor Theorem for Graphs of Small Degree (2022)

Tuukka Korhonen · Journal of Combinatorial Theory, Series B · arXiv:2203.13233

Proves the conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon in full: every graph of bounded maximum degree and sufficiently large treewidth contains a large wall or the line graph of a large wall as an induced subgraph, with explicit bounds f(k,d) = O(k^10 + 2^(d^5)).

Reviewer notes. Conjecture 3 is solved by Korhonen (arXiv:2203.13233, JCTB Vol. 160, 2023, pp. 206-214), which the paper's abstract explicitly states proves the Aboulker, Adler, Kim, Sintiari, Trotignon conjecture. The internal reference arXiv:2507.06169 concerns a different conjecture of Trotignon and is not directly relevant to Conjecture 3.

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

Conjecture. For every $d \in \mathbb{N}$ there is a function $f_d : \mathbb{N} \to \mathbb{N}$ such that every graph with degree at most $d$ and tree-width at least $f_d(k)$ contains a $(k \times k)$-wall or the line graph of a $(k \times k)$-wall as an induced subgraph.

Context

This is an induced grid theorem analogue for bounded-degree graphs, motivated by the construction of (even hole, $K_4$)-free graphs of unbounded tree-width that requires vertices of large degree and large clique minors. The conjecture is described as 'wide open' and formally implies Conjecture 2. The paper's Theorem 1.1 (the induced grid theorem for minor-free graphs) can be seen as a step in the direction of its proof.

Source paper

On the tree-width of even-hole-free graphs
Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari, Nicolas Trotignon · 2020-08-12
https://arxiv.org/abs/2008.05504 PDF source