Uniform obstruction-size 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, let C≤δ\mathbb{C}_{\leq\delta} and C<δ\mathbb{C}_{<\delta} be the corresponding class properties defined by limiting density. Uniform obstruction-size conjecture. There is a constructible function f:Q→Nf:\mathbb{Q}\to\mathbb{N} such that, for every δ∈Q\delta\in\mathbb{Q}, if G∈cobs⁡(C≤δ)\mathcal{G}\in\operatorname{cobs}(\mathbb{C}_{\leq\delta}) or G∈cobs⁡(C<δ)\mathcal{G}\in\operatorname{cobs}(\mathbb{C}_{<\delta}), then every graph in obs⁡(G)\operatorname{obs}(\mathcal{G}) has at most f(δ)f(\delta) vertices. This is proposed as a refinement of the finite obstruction conjecture, and its status is open in the supplied text.

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.