Finite obstruction conjecture for classes of a fixed limiting density

From papers

For a graph class G\mathcal{G}, let obs(G)\operatorname{obs}(\mathcal{G}) denote its minor obstruction set. For a class property C\mathbb{C}, let cobs(C)\operatorname{cobs}(\mathbb{C}) be the set of inclusion-minimal proper minor-closed graph classes not in C\mathbb{C}. For rational δ\delta, write Cδ\mathbb{C}_{\leq\delta} and C<δ\mathbb{C}_{<\delta} for the corresponding class properties defined by limiting density. Finite obstruction conjecture. For every δQ\delta\in\mathbb{Q}, both cobs(Cδ)\operatorname{cobs}(\mathbb{C}_{\leq\delta}) and cobs(C<δ)\operatorname{cobs}(\mathbb{C}_{<\delta}) are finite. The paper establishes the relevant characterization below 3/23/2 and presents finiteness for every rational density as an open research direction; the conjecture is also described as a special instance of the ω2\omega^2-well-quasi-ordering conjecture.

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

Antonios Kominatos, Reem Mahmoud and Dimitrios M. Thilikos, “Obstructions for Minor-Closed Classes of limiting Densities Below 3/2”, arXiv:2606.24326 (2026).

Solutions 0

No solutions have been posted yet.