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
DOI: https://doi.org/10.1090/S0002-9947-1995-1262340-9
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?)

  • [1] Jaroslav Nešetřil and Vojtěch Rödl, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976), no. 1, 85–95. MR 0412044
  • [2] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 0256911
  • [3] Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131
  • [4] V. Rödl and N. Sauer, The Ramsey property for families of graphs which exclude a given graph, Canad. J. Math. 44 (1992), no. 5, 1050–1060. MR 1186480, https://doi.org/10.4153/CJM-1992-064-7
  • [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. W. Sauer and X. Zhu, Graphs which do not embed a given graph and the Ramsey property, Sets, graphs and numbers (Budapest, 1991) Colloq. Math. Soc. János Bolyai, vol. 60, North-Holland, Amsterdam, 1992, pp. 631–636. MR 1218223
  • [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, https://doi.org/10.1007/BF02020444
  • [8] R. Fraïssé, Theory of relations, Studies in Logic and the Foundations of Mathematics, vol. 118, North-Holland Publishing Co., Amsterdam, 1986. Translated from the French. MR 832435
  • [9] Jaroslav Nešetřil and Vojtěch Rödl, Partitions of finite relational and set systems, J. Combinatorial Theory Ser. A 22 (1977), no. 3, 289–312. MR 0437351
  • [10] A. Gyárfás, On Ramsey covering-numbers, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, North-Holland, Amsterdam, 1975, pp. 801–816. Colloq. Math. Soc. Janós Bolyai, Vol. 10. MR 0382051
  • [11] D. P. Sumner, Subtrees of a graph and the chromatic number, The theory and applications of graphs (Kalamazoo, Mich., 1980) Wiley, New York, 1981, pp. 557–576. MR 634555
  • [12] A. Gyárfás, Problems from the world surrounding perfect graphs, Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), 1987, pp. 413–441 (1988). MR 951359
  • [13] H. A. Kierstead and S. G. Penrice, Recent results on a conjecture of Gyárfás, Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990), 1990, pp. 182–186. MR 1140509
  • [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. 1, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993, pp. 361–377. MR 1249722

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

DOI: https://doi.org/10.1090/S0002-9947-1995-1262340-9
Keywords: Graph-Ramsey theory, vertex coloring, excluded induced subgraphs
Article copyright: © Copyright 1995 American Mathematical Society