On the Ramsey property of families of graphs
Author:
N. Sauer
Journal:
Trans. Amer. Math. Soc. 347 (1995), 785833
MSC:
Primary 05C55; Secondary 05D10
MathSciNet review:
1262340
Fulltext PDF Free Access
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 twoconnected or the complements of both graphs and are twoconnected 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
(54 #173)
 [2]
Frank
Harary, Graph theory, AddisonWesley Publishing Co., Reading,
Mass.Menlo Park, Calif.London, 1969. MR 0256911
(41 #1566)
 [3]
Béla
Bollobás, Graph theory, Graduate Texts in Mathematics,
vol. 63, SpringerVerlag, New York, 1979. An introductory course. 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), no. 5,
1050–1060. MR 1186480
(94g:05059), http://dx.doi.org/10.4153/CJM19920647
 [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, NorthHolland, Amsterdam, 1992,
pp. 631–636. MR 1218223
(93m:05138)
 [7]
P.
Erdős and A.
Hajnal, On chromatic number of graphs and setsystems, Acta
Math. Acad. Sci. Hungar 17 (1966), 61–99. MR 0193025
(33 #1247)
 [8]
R.
Fraïssé, Theory of relations, Studies in Logic and
the Foundations of Mathematics, vol. 118, NorthHolland Publishing
Co., Amsterdam, 1986. Translated from the French. MR 832435
(87f:03139)
 [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
(55 #10283)
 [10]
A.
Gyárfás, On Ramsey coveringnumbers, Infinite
and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on
his 60th birthday), Vol. II, NorthHolland, Amsterdam, 1975,
pp. 801–816. Colloq. Math. Soc. Janós Bolyai, Vol. 10. MR 0382051
(52 #2939)
 [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
(83c:05047)
 [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
(89e:05089)
 [13]
H.
A. Kierstead and S.
G. Penrice, Recent results on a conjecture of
Gyárfás, Proceedings of the Twentyfirst Southeastern
Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL,
1990), 1990, pp. 182–186. 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. 1, Bolyai Soc. Math. Stud., János
Bolyai Math. Soc., Budapest, 1993, pp. 361–377. MR 1249722
(94j:05095)
 [1]
 J. Nešetřil and V. Rödl, Partitions of vertices, Comment. Math. Univ. Carolin. 17 (1976), 675681. MR 0412044 (54:173)
 [2]
 F. Harary, Graph theory, AddisonWesley Ser. in Math., AddisonWesley, 1969. MR 0256911 (41:1566)
 [3]
 B. Bollobás, Graph theory, An Introductory Course, SpringerVerlag, 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), 10501060. 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, NorthHolland, 1991, pp. 631636. 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), 6199. MR 0193025 (33:1247)
 [8]
 R. Fraïssé, Theory of relations, NorthHolland, 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), 289312. 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, NorthHolland, 1975, pp. 801816. 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. 557576. MR 634555 (83c:05047)
 [12]
 A Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. 19 (1985), 413441. 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. 361377. 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
DOI:
http://dx.doi.org/10.1090/S00029947199512623409
PII:
S 00029947(1995)12623409
Keywords:
GraphRamsey theory,
vertex coloring,
excluded induced subgraphs
Article copyright:
© Copyright 1995 American Mathematical Society
