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

From papers

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:NNf:\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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.