Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)


On the Ramsey property of families of graphs

Author: N. Sauer
Journal: Trans. Amer. Math. Soc. 347 (1995), 785-833
MSC: Primary 05C55; Secondary 05D10
MathSciNet review: 1262340
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For graphs $ A$ and $ B$ the relation $ A \to (B)_r^1$ means that for every $ r$-coloring of the vertices of $ A$ there is a monochromatic copy of $ B$ in $ A$. $ \operatorname{Forb} ({G_1},{G_2}, \ldots ,{G_n})$ is the family of graphs which do not embed any one of the graphs $ {G_1},{G_2}, \ldots ,{G_n}$, a family $ \mathcal{F}$ of graphs has the Ramsey property if for every graph $ B \in \mathcal{F}$ there is a graph $ A \in \mathcal{F}$ such that $ A \to (B)_r^1$. Nešetřil and Rödl (1976) have proven that if either both graphs $ G$ and $ K$ are two-connected or the complements of both graphs $ G$ and $ K$ are two-connected then $ \operatorname{Forb} (G,K)$ has the Ramsey property. We prove that if $ \overline G $ is disconnected and $ K$ is disconnected then $ \operatorname{Forb} (G,K)$ does not have the Ramsey property, except for four pairs of graphs $ (G,K)$.

A family $ \mathcal{F}$ of finite graphs is an age if there is a countable graph $ G$ whose set of finite induced subgraphs is $ \mathcal{F}$. We characterize those pairs of graphs $ (G,H)$ for which $ \operatorname{Forb} (G,H)$ is not an age but has the Ramsey property.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C55, 05D10

Retrieve articles in all journals with MSC: 05C55, 05D10

Additional Information

PII: S 0002-9947(1995)1262340-9
Keywords: Graph-Ramsey theory, vertex coloring, excluded induced subgraphs
Article copyright: © Copyright 1995 American Mathematical Society