PDF
Discussiones
Mathematicae Graph Theory 19(2) (1999) 135-142
DOI: https://doi.org/10.7151/dmgt.1090
A NOTE ON THE RAMSEY NUMBER AND THE PLANAR RAMSEY NUMBER FOR C4 AND COMPLETE GRAPHS
Halina Bielak
Institute of Mathematics UMCS
M. Curie-Sk odowska University
Lublin, Poland
e-mail: hbiel@golem.umcs.lublin.pl
Abstract
We give a lower bound for the Ramsey number and the planar Ramsey number for C4 and complete graphs. We prove that the Ramsey number for C4 and K7 is 21 or 22. Moreover we prove that the planar Ramsey number for C4 and K6 is equal to 17.
Keywords: planar graph, Ramsey number.
1991 Mathematics Subject Classification: 05C55.
References
| [1] | H. Bielak, I. Gorgol, The Planar Ramsey Number for C4 and K5 is 13, to appear in Discrete Math. |
| [2] | H. Bielak, Ramsey-Free Graphs of Order 17 for C4 and K6, submitted. |
| [3] | J.A. Bondy, P. Erdős, Ramsey Numbers for Cycles in Graphs, J. Combin. Theory (B) 14 (1973) 46-54, doi: 10.1016/S0095-8956(73)80005-X. |
| [4] | V. Chvátal, F. Harary, Generalized Ramsey Theory for Graphs, III. Small Off-Diagonal Numbers, Pacific J. Math. 41 (1972) 335-345. |
| [5] | M. Clancy, Some Small Ramsey Numbers, J. Graph Theory 1 (1977) 89-91, doi: 10.1002/jgt.3190010117. |
| [6] | P. Erdős, R.J. Faudree, C.C. Rousseau, R.H. Schelp, On Cycle-Complete Graph Ramsey Numbers, J. Graph Theory 2 (1978) 53-64, doi: 10.1002/jgt.3190020107. |
| [7] | C.C. Rousseau, C.J. Jayawardene, The Ramsey number for a quadrilateral vs. a complete graph on six vertices, Congressus Numerantium 123 (1997) 97-108. |
| [8] | R. Steinberg, C.A. Tovey, Planar Ramsey Number, J. Combin. Theory (B) 59 (1993) 288-296, doi: 10.1006/jctb.1993.1070. |
| [9] | K. Walker, The Analog of Ramsey Numbers for Planar Graphs, Bull. London Math. Soc. 1 (1969) 187-190, doi: 10.1112/blms/1.2.187. |
Received 20 January 1999
Revised 4 October 1999
Close