Logarithmic treewidth of (even hole, Kₜ)-free graphs

Status solved high confidence

Conjecture 1.7 from arXiv:2305.16258, asserting that (even hole, $K_t$)-free graphs have logarithmic treewidth, was proved in arXiv:2402.14211 (Chudnovsky, Gartland, Hajebi, Lokshtanov, Spirkl, 2024). That paper establishes that for every integer $t\geq 1$ there exists a constant $c_t$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t \log n$, resolving Conjecture 1.2 of Sintiari and Trotignon and matching the 'upcoming preprint by some of the same authors' referenced in the source paper. The logarithmic bound is asymptotically best possible.

Cited literature (1)

• proof Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth (2024)
  Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl · arXiv preprint · arXiv:2402.14211

  Proves that for every integer t≥1 there exists c_t such that every n-vertex even-hole-free graph with no clique of size t has treewidth at most c_t log n, directly establishing the conjecture.

Reviewer notes. arXiv:2402.14211 is almost certainly the 'upcoming preprint by some of the same authors' referenced in the source paper: its authors include Chudnovsky, Hajebi, and Spirkl, who are also co-authors of 2305.16258. The proved statement coincides with Conjecture 1.2 of Sintiari and Trotignon. No internal references were supplied for this conjecture.

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