On the Ramsey property of families of graphs
HTML articles powered by AMS MathViewer
- by N. Sauer PDF
- Trans. Amer. Math. Soc. 347 (1995), 785-833 Request permission
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
- Jaroslav Ne et il and Vojtěch Rödl, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976), no. 1, 85–95. MR 412044
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
- Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131
- 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, DOI 10.4153/CJM-1992-064-7 V. Rödl, N. Sauer, and X. Zhu, Ramsey families which exclude a graph, Yellow series, no. 708, Dept. of Math., Univ of Calgary.
- 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
- P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. MR 193025, DOI 10.1007/BF02020444
- 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
- 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 437351, DOI 10.1016/0097-3165(77)90004-8
- 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, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 801–816. MR 0382051
- 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
- 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
- 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 —, Radius two trees specify $\chi$-bounded classes, J. Graph Theory (to appear).
- 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, DOI 10.1080/07468342.1993.11973559
Additional Information
- © Copyright 1995 American Mathematical Society
- 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