The Solidity Conjecture for universal graphs with a forbidden graph

Let CC be a finite or countable graph with no isolated vertices. Decompose CC into its blocks, where each block is a 2-connected component, and let C~\tilde C be the underlying forest whose vertices are the blocks of CC, with adjacency determined by sharing a vertex. A graph is CC-free if it contains no copy of CC, and a universal graph may be universal either in the weak or strong sense. Solidity Conjecture. If there is a CC-free universal graph, in either the weak or strong sense, then every block of CC is complete. This conjecture asserts that the existence of a universal graph avoiding one finite connected constraint forces the constraint's block structure to be solid. The supplied text gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Gregory Cherlin and Saharon Shelah, “Universal graphs with a forbidden subtree”, arXiv:math/0512218 (2005).

Progress summary

Never refreshed

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.