Sintiari and Trotignon's bounded-treewidth conjecture for even-hole-free graphs
For a graph , a tree decomposition consists of a tree and a map satisfying the usual vertex coverage, edge coverage, and connectedness conditions. The treewidth of , denoted by , is the minimum, over all tree decompositions of , 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 , there exists a constant such that every even-hole-free graph with no diamond and no clique of size satisfies
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
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.