The Reduction Conjecture for universal graphs
Let be a finite or countable graph with no isolated vertices, and decompose it into blocks, its 2-connected components. Let be the underlying tree of : its vertices are the blocks of , and two vertices are adjacent when the corresponding blocks share a common vertex. A graph is -free if it contains no copy of , and universality is understood in either the weak or strong sense. Reduction Conjecture. If there is a -free universal graph, in either sense, then there is a -free universal graph, where is the underlying tree of . The conjecture would reduce universality questions for forbidden connected graphs to universality questions for their underlying trees. The supplied text gives no resolution, so the conjecture remains open.
References
- Gregory Cherlin and Saharon Shelah, “Universal graphs with a forbidden subtree”, arXiv:math/0512218 (2005).
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
No solutions have been posted yet.