# Universal graphs with a forbidden subtree

@article{Cherlin2007UniversalGW, title={Universal graphs with a forbidden subtree}, author={Gregory L. Cherlin and Saharon Shelah}, journal={J. Comb. Theory, Ser. B}, year={2007}, volume={97}, pages={293-333} }

We show that the problem of the existence of universal graphs with specified forbidden subgraphs can be systematically reduced to certain critical cases by a simple pruning technique which simplifies the underlying structure of the forbidden graphs, viewed as trees of blocks. As an application, we characterize the trees T for which a universal countable T-free graph exists.

#### Topics from this paper

#### 13 Citations

Universal graphs with forbidden subgraphs

- 2005

The graph theoretic problem of identifying the finite sets C of constraint graphs for which there is a countable universal C-free graph is closely related to the problem of determining for which sets… Expand

Universal graphs with a forbidden subgraph: Block path solidity

- Mathematics, Computer Science
- Comb.
- 2016

This generalizes a result of Füredi and Komjáth, and fits naturally into a set of conjectures regarding the existence of countable C-free graphs, with C an arbitrary finite connected graph. Expand

Universal graphs with a forbidden near-path or 2-bouquet

- Mathematics
- 2007

We consider the problem of the existence of universal countable C-free graphs with C a connected finite graph. For C a tree arising by from a path by adjunction of one additional edge we show that a… Expand

Multicoloured Random Graphs: Constructions and Symmetry

- Mathematics
- 2015

This is a research monograph on constructions of and group actions on countable homogeneous graphs, concentrating particularly on the simple random graph and its edge-coloured variants. We study… Expand

Structural Ramsey Theory and the Extension Property for Partial Automorphisms

- Mathematics, Computer Science
- 2020

We survey recent developments concerning two properties of classes of finite structures: the Ramsey property and the extension property for partial automorphisms (EPPA).

Structural Ramsey Theory and the Extension Property for Partial Automorphisms

- Mathematics, Computer Science
- ArXiv
- 2020

We survey recent developments concerning two properties of classes of finite structures: the Ramsey property and the extension property for partial automorphisms (EPPA).

Forbidden substructures and combinatorial dichotomies: WQO and universality

- Computer Science, Mathematics
- Discret. Math.
- 2011

The ''Hairy Ball Problem'' is pointed to as a particularly concrete problem, which is given first in direct model theoretic terms, and then decoded as an explicit graph theoretic problem. Expand

Divide and Conquer: Dividing Lines and Universality

- Computer Science
- 2021

There is much on conjectures, problems and old results, mainly of the author and also on some recent results on dividing lines (in model theory) and some test questions, mainly the universality spectrum. Expand

All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)

- Computer Science, Mathematics
- Advances in Mathematics
- 2019

The Ramsey property for classes of ordered structures with closures and given local properties is proved, providing the ultimate generalisation of the structural Ramsey theorem. Expand

Biologically Unavoidable Sequences

- Mathematics, Computer Science
- Electron. J. Comb.
- 2013

It is shown that every eventually periodic sequence is biologically unavoidable (this generalizes Koenig's Lemma), and some biologically avoidable sequences are exhibited. Expand

#### References

SHOWING 1-10 OF 23 REFERENCES

Universal Graphs with Forbidden Subgraphs and Algebraic Closure

- Mathematics
- 1998

We apply model theoretic methods to the problem of existence of countable universal graphs with finitely many forbidden connected subgraphs. We show that to a large extent the question reduces to one… Expand

Forbidden subgraphs and forbidden substructures

- Computer Science, Mathematics
- Journal of Symbolic Logic
- 2001

Abstract The problem of the existence of a universal structure omitting a finite set of forbidden substructures is reducible to the corresponding problem in the category of graphs with a vertex… Expand

Some universal graphs

- Mathematics
- 1988

It is shown that various classes of graphs have universal elements. In particular, for eachn the class of graphs omitting all paths of lengthn and the class of graphs omitting all circuits of length… Expand

Some remarks on universal graphs

- Mathematics, Computer Science
- Discret. Math.
- 1999

There is no universal countable H-free graph if H is the dispoint union of 3 or more complete n-cliques for some n ⩾ 2, plus one vertex, joined to every other point. Expand

Graphs omitting a finite set of cycles

- Computer Science
- J. Graph Theory
- 1996

We prove that for C a finite set of cycles, there is a universal C-free graph if and only if C consists precisely of all the odd cycles of order less than same specified bound. The sufficiency of… Expand

Nonexistence of universal graphs without some trees

- Mathematics, Computer Science
- Comb.
- 1997

IfG is a finite tree with a unique vertex of largest, and ≥4 degree which is adjacent to a leaf then there is no universal countableG-free graph.

Universal graphs without large bipartite subgraphs

- Mathematics
- 1984

Keywords: infinite graphs ; universal graph ; forbidden subgraphs Note: Professor Pach's number: [034] Reference DCG-ARTICLE-1984-005 Record created on 2008-11-14, modified on 2017-05-12

A Problem of Ulam on Planar Graphs

- Computer Science, Mathematics
- Eur. J. Comb.
- 1981

The following problem was raised by S. M. Ulam: Does there exist a countable planar graph Go such that every countable planar graph is isomorphic to a subgraph of G 0 ? We answer this question in the… Expand

Universal elements and the complexity of certain classes of infinite graphs

- Computer Science, Mathematics
- Discret. Math.
- 1991

A class of graphs has a universal element G0, if every other element of the class is isomorphic to an induced subgraph of G0. In Sections 1?4 we give a survey of some recent developments in the… Expand