Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 432.05038
Autor: Burr, Stefan A.; Erdös, Paul; Faudree, Ralph J.; Schelp, R.H.
Title: A class of Ramsey-finite graphs. (In English)
Source: Proc. 9th southeast. Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 171-180 (1978).
Review: [For the entire collection see Zbl 396.00003.]
The notation F ––> (G,H) is used to imply that if the edges of Fare colored with two colors, say red and blue, then either there exists a red copy of G or a blue copy of H. The class of all graphs F or which F ––> (G,H) is denoted R'(G,H). The class of minimal graphs in R'(G,H) is denoted R(G,H). The authors show that if G is an aritrary graph on n vertices and m is a positive integer, then whenever F in R(mK2,G), we always have |E(F)| \leq sumi = 1bni where b = (m-1)(\binom{2m-1}{2})+1)+1. As a corollary, they conclude that he class R(mK2,G) is finite. It should be noted that there are large classes of graphs for which R(G,H) is infinite but few nontrivial examples are known where R(G,H) is finite.
Reviewer: W.T.Trotter
Classif.: * 05C55 Generalized Ramsey theory
Keywords: minimal graphs
Citations: Zbl.396.00003
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag