Dallard–Milanič–Štorgel tree-independence conjecture for hereditary classes

At least 2 years old · documented by

Let G\mathcal{G} be a hereditary class of graphs. A class has bounded tree-independence number if there is a constant c∈Nc\in\mathbb{N} such that every graph in the class admits a tree decomposition whose bags induce subgraphs with no stable set on c+1c+1 vertices; it is (tw⁡,ω)(\operatorname{{\sf tw}},\omega)-bounded if there is a function f:N→Nf:\mathbb{N}\to\mathbb{N} such that tw⁡(G)≤f(ω(G))\operatorname{{\sf tw}}(G)\leq f(\omega(G)) for every graph GG in the class. The tree-independence number is denoted by tree−α⁡(G)\operatorname{{\text{\sf{tree}}-\alpha}}(G). Dallard–Milanič–Štorgel's conjecture. A hereditary class G\mathcal{G} has bounded tree−α⁡\operatorname{{\text{\sf{tree}}-\alpha}} if and only if G\mathcal{G} is (tw⁡,ω)(\operatorname{{\sf tw}},\omega)-bounded. Chudnovsky and Trotignon refuted this conjecture: there are hereditary (tw⁡,ω)(\operatorname{{\sf tw}},\omega)-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

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.