Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht forbidden-subgraph characterization

Let F\mathcal{F} be a finite class of graphs, and let F\mathcal{F}-free mean having no induced subgraph isomorphic to a member of F\mathcal{F}. A multiclaw is a graph each component of which is isomorphic to an induced subgraph of K1,3K_{1,3}; a subdivided multiclaw is a subdivision of such a graph, and its line graph has one vertex for each edge with adjacency inherited from edge incidence. 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 there exist F1,F2,F3FF_1,F_2,F_3\in\mathcal{F} where F1F_1 is complete bipartite, F2F_2 is a subdivided multiclaw, and F3F_3 is the line graph of a subdivided multiclaw. The paper identifies this as an equivalent formulation of the finite-forbidden-subgraph conjecture and then proves the conjecture.

Sources & referencesView supporting material

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.