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

Abstract | References | Similar Articles | Additional Information

Abstract: For graphs and the relation means that for every -coloring of the vertices of there is a monochromatic copy of in . is the family of graphs which do not embed any one of the graphs , a family of graphs has the Ramsey property if for every graph there is a graph such that . Nešetřil and Rödl (1976) have proven that if either both graphs and are two-connected or the complements of both graphs and are two-connected then has the Ramsey property. We prove that if is disconnected and is disconnected then does not have the Ramsey property, except for four pairs of graphs .

A family of finite graphs is an *age* if there is a countable graph whose set of finite induced subgraphs is . We characterize those pairs of graphs for which is not an age but has the Ramsey property.

**[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*-*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**

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