The Solidity Conjecture for universal graphs with a forbidden graph
The Solidity Conjecture for universal graphs with a forbidden graph
Let be a finite or countable graph with no isolated vertices. Decompose into its blocks, where each block is a 2-connected component, and let be the underlying forest whose vertices are the blocks of , with adjacency determined by sharing a vertex. A graph is -free if it contains no copy of , and a universal graph may be universal either in the weak or strong sense. Solidity Conjecture. If there is a -free universal graph, in either the weak or strong sense, then every block of 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
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.