Quadratic universal graph conjecture for bipartite permutation graphs
Quadratic universal graph conjecture for bipartite permutation graphs
For each positive integer , let be a bipartite permutation graph containing every bipartite permutation graph on vertices as an induced subgraph, and let 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 -vertex bipartite permutation graphs is
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.