Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht conjecture for finitely forbidden induced subgraphs

Let F\mathcal{F} be a finite class of graphs. A graph is F\mathcal{F}-free if it has no induced subgraph isomorphic to any member of F\mathcal{F}. The class of all F\mathcal{F}-free graphs 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 such graph; bounded tree−α⁡\operatorname{{\text{\sf{tree}}-\alpha}} means that their tree decompositions have bags with bounded independence number. Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht's conjecture. The class of all F\mathcal{F}-free graphs has bounded tree−α⁡\operatorname{{\text{\sf{tree}}-\alpha}} if and only if it is (tw⁡,ω)(\operatorname{{\sf tw}},\omega)-bounded. This is a restriction of the broader hereditary-class conjecture and is presented as a conjecture before being proved in the paper.

References

Primary source

Sepehr Hajebi and Sophie Spirkl, “Tree-alpha and excluding finitely many graphs”, arXiv:2605.01223 (2026).

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.