Universal bounded-degree graph conjecture
Universal bounded-degree graph conjecture
Let be the family of all graphs on vertices with maximum degree . A graph is -universal if it contains every member of a graph family . Let be the binomial random graph.
Universal bounded-degree graph conjecture. Let and . Then, with high probability, is -universal.
This strengthens the preceding embedding conjecture by requiring one random graph to contain every graph on vertices of maximum degree at most . The proposed density is motivated by the conjectured worst case of -factors, but the statement remains open in the source.
Sources & referencesView supporting material
Primary source
Asaf Ferber, Kyle Luh and Oanh Nguyen, “Embedding large graphs into a random graph”, arXiv:1606.05923 (2017).
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.