Dallard–Milanič–Štorgel tree-independence conjecture for hereditary classes
Let be a hereditary class of graphs. A class has bounded tree-independence number if there is a constant such that every graph in the class admits a tree decomposition whose bags induce subgraphs with no stable set on vertices; it is -bounded if there is a function such that for every graph in the class. The tree-independence number is denoted by . Dallard–Milanič–Štorgel's conjecture. A hereditary class has bounded if and only if is -bounded. Chudnovsky and Trotignon refuted this conjecture: there are hereditary -bounded classes whose bounding functions can grow arbitrarily fast, so the asserted equivalence fails.
References
Primary source
Sepehr Hajebi and Sophie Spirkl, “Tree-alpha and excluding finitely many graphs”, arXiv:2605.01223 (2026).
Additional references
6 papers in this index state this conjecture (2023–2026). The statement above is taken from the most recent of them; the others are arXiv:2510.19120, arXiv:2501.14658, arXiv:2405.07471, arXiv:2308.05817, arXiv:2305.16258.
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.