Quadratic universal graph conjecture for bipartite permutation graphs

For each positive integer nn, let UnU_n be a bipartite permutation graph containing every bipartite permutation graph on nn vertices as an induced subgraph, and let u(n)u(n) be the minimum possible number of vertices of such a universal graph.

Quadratic universal graph conjecture. The minimum number of vertices in a bipartite permutation graph containing all nn-vertex bipartite permutation graphs is

Ω(n2).\Omega(n^2).

This conjecture asserts that the optimal universal bipartite permutation graph has quadratic size, matching the intended order of the known construction.

Sources & referencesView supporting material

Primary source

Bogdan Alecu, Vadim Lozin and Dmitriy Malyshev, “Critical properties of bipartite permutation graphs”, arXiv:2010.14467 (2020).

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.