Universal graphs with a forbidden subgraph: Block path solidity

2014/04/23 by Gregory Cherlin, Saharon Shelah, Cherlin, Gregory +1 · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Advanced Topology and Set Theory

paper · pdf · doi:10.48550/arxiv.1404.5757

Abstract

Let C be a finite connected graph for which there is a countable universal C-free graph, and whose tree of blocks is a path. Then the blocks of C are complete. This generalizes a result of Furedi and Komjath, and fits naturally into a set of conjectures regarding the existence of countable C-free graphs, with C an arbitrary finite connected graph.

Cited by

• Smaller universal posets
• Structural Ramsey Theory and the Extension Property for Partial\n Automorphisms

Related

• Universal graphs with a forbidden subtree
• Universal graphs with forbidden subgraphs and algebraic closure
• Universality vs Genericity and C₄-free graphs
• Universal bridge-free graphs
• There is no universal countable random-free graph