Uniform obstruction-size 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, 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:QNf:\mathbb{Q}\to\mathbb{N} such that, for every δQ\delta\in\mathbb{Q}, if Gcobs(Cδ)\mathcal{G}\in\operatorname{cobs}(\mathbb{C}_{\leq\delta}) or Gcobs(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.

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.