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]**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*-*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)**

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