Bounded-degree even-hole-free tree-width

Conjecture 2 · 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 2 from arXiv:2008.05504 — that every even-hole-free graph of degree at most $d$ has tree-width at most $f(d)$ for some function $f$ — was resolved affirmatively within weeks of being posted. Abrishami, Chudnovsky, and Vušković (arXiv:2009.01297, submitted September 2020) proved the full statement by showing that decomposition cutsets in even-hole-free bounded-degree graphs can be organized into a bounded number of well-behaved collections, yielding bounded treewidth. The internal reference arXiv:2108.01162 addresses a related but distinct conjecture about unavoidable induced subgraphs in bounded-degree graphs; arXiv:2507.06169 provides a counterexample to a different conjecture of Trotignon about outerstring induced subgraphs, not to Conjecture 2.

Cited literature (1)

proof Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree (2020)

Tara Abrishami, Maria Chudnovsky, Kristina Vušković · arXiv preprint · arXiv:2009.01297

Proves the full conjecture: every even-hole-free graph with bounded degree has bounded treewidth, resolving the conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon.

Reviewer notes. Conjecture 2 was proved by Abrishami, Chudnovsky, and Vušković in arXiv:2009.01297, submitted 2020-09-02, just three weeks after the source paper appeared. A ScienceDirect search result (pii S0095895622000533) suggests the paper was subsequently published in the Journal of Combinatorial Theory, Series B, but the DOI was not verified via WebFetch within the 5-call cap.

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

Conjecture. There is a function $f : \mathbb{N} \to \mathbb{N}$ such that every even-hole-free graph of degree at most $d$ has tree-width at most $f(d)$.

Context

The class of even-hole-free graphs has unbounded tree-width in general (e.g., complete graphs and chordal graphs). Bounded degree is conjectured to be a sufficient structural restriction. If true, it would imply that even-hole-freeness is testable with constant query complexity and polylogarithmic running time in the bounded-degree graph model, via CMSO testability on bounded tree-width graphs. The paper proves the conjecture for $d \leq 3$ (subcubic graphs) and proves a weakening for $d = 4$.

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