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

About 3 years old · traced to

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.

References

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.