Universal graphs with a forbidden subgraph: block path solidity

DOI10.1007/S00493-014-3181-5MaRDI QIDQ1677537zbMATH OpenOpenAlexFDO

Authors Gregory Cherlin, S. Shelah

Publication date 10 November 2017

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5757

zbMATH Keywords

block pathconnected graphforbidden subgraph

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Infinite graphs (05C63)

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.

Recommendations

• On the existence of countable universal graphs
• There is no universal countable pentagon‐free graph
• Universal graphs with a forbidden subtree
• Graphs omitting a finite set of cycles
• Universal graphs with a forbidden near‐path or 2‐bouquet

Cites work

• A family of countable homogeneous graphs
• Club guessing and the universal models
• On the existence of countable universal graphs
• Universal elements and the complexity of certain classes of infinite graphs
• Universal graphs with a forbidden near‐path or 2‐bouquet
• Universal graphs with a forbidden subtree

Cited in

(10)

• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• Universal graphs omitting finitely many finite graphs
• Bowtie-free graphs have a Ramsey lift
• More on the revised GCH and the black box
• On the existence of countable universal graphs
• Ramsey properties and extending partial automorphisms for classes of finite structures
• Universal graphs with a forbidden near‐path or 2‐bouquet
• A note on classes of subgraphs of locally finite graphs
• Universal graphs for the topological minor relation
• Universal graphs between a strong limit singular and its power

This page was built for publication: Universal graphs with a forbidden subgraph: block path solidity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1677537)