The universality conjecture for finite connected graph minor classes

About 3 years old · traced to

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.

References

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.