Sintiari and Trotignon's bounded-treewidth conjecture for even-hole-free graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.