The Reduction Conjecture for universal graphs

From papers

Let CC be a finite or countable graph with no isolated vertices, and decompose it into blocks, its 2-connected components. Let C~\tilde C be the underlying tree of CC: its vertices are the blocks of CC, and two vertices are adjacent when the corresponding blocks share a common vertex. A graph is CC-free if it contains no copy of CC, and universality is understood in either the weak or strong sense. Reduction Conjecture. If there is a CC-free universal graph, in either sense, then there is a C~\tilde C-free universal graph, where C~\tilde C is the underlying tree of CC. 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

No solutions have been posted yet.