DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 135-142
DOI: 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