A note on the Ramsey number and the planar Ramsey number for C₄ and complete graphs

Halina Bielak

ArticleOriginal scientific text

Title

A note on the Ramsey number and the planar Ramsey number for C₄ and complete graphs

Authors ¹

Affiliations

Institute of Mathematics UMCS, M. Curie-Skłodowska University, Lublin, Poland

Abstract

We give a lower bound for the Ramsey number and the planar Ramsey number for C₄ and complete graphs. We prove that the Ramsey number for C₄ and K₇ is 21 or 22. Moreover we prove that the planar Ramsey number for C₄ and K₆ is equal to 17.

Keywords

ENG

planar graph, Ramsey number

H. Bielak, I. Gorgol, The Planar Ramsey Number for C₄ and K₅ is 13, to appear in Discrete Math.
H. Bielak, Ramsey-Free Graphs of Order 17 for C₄ and K₆, submitted.
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.
V. Chvátal, F. Harary, Generalized Ramsey Theory for Graphs, III. Small Off-Diagonal Numbers, Pacific J. Math. 41 (1972) 335-345.
M. Clancy, Some Small Ramsey Numbers, J. Graph Theory 1 (1977) 89-91, doi: 10.1002/jgt.3190010117.
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.
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.
R. Steinberg, C.A. Tovey, Planar Ramsey Number, J. Combin. Theory (B) 59 (1993) 288-296, doi: 10.1006/jctb.1993.1070.
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.

Title

A note on the Ramsey number and the planar Ramsey number for C₄ and complete graphs

Affiliations

Abstract

Keywords

Bibliography