The universality conjecture for finite connected graph minor classes

Let XX be a finite connected graph. A graph is strongly universal for a class of graphs if every graph in the class appears as a subgraph of it, and weakly universal if every graph in the class appears as a minor of it. An XX-minor-free graph is a graph with no minor isomorphic to XX.

Universality conjecture. The following are equivalent:

There is a strongly universal X-minor-free graph;\text{There is a strongly universal }X\text{-minor-free graph}; There is a weakly universal X-minor-free graph;\text{There is a weakly universal }X\text{-minor-free graph}; X is planar.X\text{ is planar}.

This conjecture would characterize exactly the finite connected graphs whose minor-closed classes admit universal graphs in either sense. The surrounding discussion notes several positive and negative results, but the equivalence is not established in general.

Sources & referencesView supporting material

Primary source

Thilo Krill, “Universal graphs with forbidden wheel minors”, arXiv:2309.12473 (2023).

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.