Simple proof of the existence of restricted ramsey graphs by means of a partite construction
Tóm tắt
By means of a partite construction we present a short proof of the Galvin Ramsey property of the class of all finite graphs and of its strengthening proved in [5]. We also establish a generalization of those results. Further we show that for every positive integerm there exists a graphH which is Ramsey forK
m and does not contain two copies ofK
m with more than two vertices in common.
Tài liệu tham khảo
W. Deuber, Generalizations of Ramsey’s theorem, in:Infinite and Finite Sets (A. Hajnal et al, eds.),Colloquia Mathematica Societatis J. Bolyai 10, North-Holland (1975), 323–332.
P. Erdős, A. Hajnal andL. Pósa, Strong embeddings of graphs into colored graphs, in:Infinite and finite sets (A. Hajnal et al., eds.)Coll. Math. Soc. J. Bolyai 10, North-Holland (1975), 1127–1132.
P. Erdős, Problems and results on finite and infinite graphs, in:Recent advances in graph theory, Academia Praha (1975), 183–192.
J. Folkman, Graphs with monochromatic complete subgraphs in every edge coloring,SIAM J. Appl. Math. 18 (1970), 19–29.
J. Nešetřil andV. Rödl, The Ramsey property for graphs with forbidden complete subgraphs,J. Comb. Theory B 20 (1976), 243–249.
J. Nešetřil andV. Rödl, A short constructive proof of the existence of highly chromatic graphs without short cycles,J. Comb. Theory B 27 (1979) 225–227.
J. Nešetřil andV. Rödl, A simple proof of the Galvin Ramsey property of the class of all finite graphs and a dimension of a graph,Discrete Mathematics 23 (1978), 49–55.
J. Nešetřil andV. Rödl, Partition (Ramsey) theory — a survey, in:Combinatorics (A. Hajnal and Vera T. Sós, eds.)Coll. Math. Soc. J. Bolyai 18, North-Holland (1978), 759–792.
J. Nešetřil andV. Rödl, Partition theory and its application, in:Surveys in Combinatorics, (B. Bollobás, ed.)London Math. Soc. Lecture Notes 38, Cambridge Univ. Press 1979, 96–156.
F. P. Ramsey, On a problem of formal logic,Proc. London Math. Soc. 30 (1930), 264–286.
V. Rödl, A generalization of Ramsey theorem, in:Graphs, Hypergraphs and Block Systems, Zielona Gora (1976), 211–220.