The Reduction Conjecture for universal graphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Gregory Cherlin and Saharon Shelah, “Universal graphs with a forbidden subtree”, arXiv:math/0512218 (2005).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.