Sintiari and Trotignon's bounded-treewidth conjecture for even-hole-free graphs

For a graph G=(V(G),E(G))G=(V(G),E(G)), a tree decomposition (T,χ)(T,\chi) consists of a tree TT and a map χ:V(T)2V(G)\chi:V(T)\to 2^{V(G)} satisfying the usual vertex coverage, edge coverage, and connectedness conditions. The treewidth of GG, denoted by tw(G)\operatorname{tw}(G), is the minimum, over all tree decompositions of GG, of the maximum bag size minus one. A hole is an induced cycle with at least four vertices; it is even if its length is even. A diamond is the unique simple graph with four vertices and five edges. Sintiari and Trotignon's conjecture. For every integer tt, there exists a constant ctc_t such that every even-hole-free graph GG with no diamond and no clique of size tt satisfies

tw(G)ct.\operatorname{tw}(G)\leq c_t.

The conjecture asserts bounded treewidth for even-hole-free graphs under the stated exclusions, motivated by the existence of even-hole-free graphs of arbitrarily large treewidth when these restrictions are absent. Its resolution status is not specified in the supplied source material.

Sources & referencesView supporting material

Primary source

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi and Sophie Spirkl, “Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs”, arXiv:2307.13684 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.