The Solidity Conjecture for universal graphs with a forbidden graph

About 21 years old · traced to

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.

References

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.