Remote Access Transactions of the American Mathematical Society
Green Open Access

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

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?)

  • [1] J. Nešetřil and V. Rödl, Partitions of vertices, Comment. Math. Univ. Carolin. 17 (1976), 675-681. MR 0412044 (54:173)
  • [2] F. Harary, Graph theory, Addison-Wesley Ser. in Math., Addison-Wesley, 1969. MR 0256911 (41:1566)
  • [3] B. Bollobás, Graph theory, An Introductory Course, Springer-Verlag, 1979. MR 536131 (80j:05053)
  • [4] V. Rödl and N. Sauer, The Ramsey property for families of graphs which exclude a given graph, Canad. J. Math. 44 (1992), 1050-1060. MR 1186480 (94g:05059)
  • [5] V. Rödl, N. Sauer, and X. Zhu, Ramsey families which exclude a graph, Yellow series, no. 708, Dept. of Math., Univ of Calgary.
  • [6] N. Sauer and X. Zhu, Graphs which do not embed a given graph and the Ramsey property, Sets, Graphs and Numbers, Colloq. Math. Soc. János Bolyai, vol. 60, North-Holland, 1991, pp. 631-636. MR 1218223 (93m:05138)
  • [7] P. Erdős and A. Hajnal, On chromatic number of graphs and set systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61-99. MR 0193025 (33:1247)
  • [8] R. Fraïssé, Theory of relations, North-Holland, 1986. MR 832435 (87f:03139)
  • [9] J. Nešetřil and V. Rödl, Partitions of finite relational and set systems, J. Combin. Theory Ser. A 22 (1977), 289-312. MR 0437351 (55:10283)
  • [10] A Gyárfás, On Ramsey covering numbers, Infinite and Finite Sets, Colloq. Math. Soc. János Bolyai, vol. 10, North-Holland, 1975, pp. 801-816. MR 0382051 (52:2939)
  • [11] D. P. Sumner, Subtrees of a graph and chromatic number, The Theory of Applications of Graphs (Gary Chartrand, ed.), Wiley, 1981, pp. 557-576. MR 634555 (83c:05047)
  • [12] A Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. 19 (1985), 413-441. MR 951359 (89e:05089)
  • [13] H. Kierstead and S. Penrice, Recent results on a conjecture of Gyárfás, preprint. MR 1140509 (92m:05084)
  • [14] -, Radius two trees specify $ \chi $-bounded classes, J. Graph Theory (to appear).
  • [15] N. Sauer, Vertex partition problems, Combinatorics, Paul Erdős is Eighty, Vol. I, Kesthely, Hungary, 1993, pp. 361-377. MR 1249722 (94j:05095)

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

Keywords: Graph-Ramsey theory, vertex coloring, excluded induced subgraphs
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society