Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht forbidden-subgraph characterization
Dallard–Krnc–Kwon–Milanič–Munaro–Štorgel–Wiederrecht forbidden-subgraph characterization
Let be a finite class of graphs, and let -free mean having no induced subgraph isomorphic to a member of . A multiclaw is a graph each component of which is isomorphic to an induced subgraph of ; 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 -free graphs has bounded if and only if there exist where is complete bipartite, is a subdivided multiclaw, and 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.