Finite obstruction conjecture for classes of a fixed limiting density

Less than 1 year old · traced to

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.

References

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).

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.