PDF
Discussiones Mathematicae Graph Theory 25(1-2) (2005)
129-139
DOI: https://doi.org/10.7151/dmgt.1267
THE CYCLE-COMPLETE GRAPH RAMSEY NUMBER R(C5,K7)
Ingo Schiermeyer
Institut für Diskrete Mathematik und Algebra
Technische Universität Bergakademie Freiberg
09596 Freiberg, Germany
e-mail: schierme@tu-freiberg.de
Abstract
The cycle-complete graph Ramsey number r(Cm,Kn) is the smallest integer N such that every graph G of order N contains a cycle Cm on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erdős, Faudree, Rousseau and Schelp that r(Cm,Kn) = (m−1)(n−1)+1 for all m ≥ n ≥ 3 (except r(C3,K3) = 6). This conjecture holds for 3 ≤ n ≤ 6. In this paper we will present a proof for r(C5,K7) = 25.Keywords: Ramsey numbers, extremal graphs.
2000 Mathematics Subject Classification: 05C55, 05C35.
References
[1] | J.A. Bondy and 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. |
[2] | B. Bollobás, C.J. Jayawardene, Z.K. Min, C.C. Rousseau, H.Y. Ru and J. Yang, On a conjecture involving cycle-complete graph Ramsey numbers, Australas. J. Combin. 22 (2000) 63-72. |
[3] | J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). |
[4] | V. Chvátal and P. Erdős, A note on hamiltonian circuits, Discrete Math. 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9. |
[5] | P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, On cycle-complete graph Ramsey numbers, J. Graph Theory 2 (1978) 53-64, doi: 10.1002/jgt.3190020107. |
[6] | R.J. Faudree and R.H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974) 313-329, doi: 10.1016/0012-365X(74)90151-4. |
[7] | C.J. Jayawardene and C.C. Rousseau, The Ramsey number for a qudrilateral versus a complete graph on six vertices, Congr. Numer. 123 (1997) 97-108. |
[8] | C.J. Jayawardene and C.C. Rousseau, The Ramsey Number for a Cycle of Length Five vs. a Complete Graph of Order Six, J. Graph Theory 35 (2000) 99-108, doi: 10.1002/1097-0118(200010)35:2<99::AID-JGT4>3.0.CO;2-6. |
[9] | V. Nikiforov, The cycle-complete graph Ramsey numbers, preprint 2003, Univ. of Memphis. |
[10] | S.P. Radziszowski, Small Ramsey numbers, Elec. J. Combin. 1 (1994) DS1. |
[11] | S.P. Radziszowski and K.-K. Tse, A Computational Approach for the Ramsey Numbers R(C4,Kn), J. Comb. Math. Comb. Comput. 42 (2002) 195-207. |
[12] | V. Rosta, On a Ramsey Type Problem of J.A. Bondy and P. Erdős, I & II, J. Combin. Theory (B) 15 (1973) 94-120, doi: 10.1016/0095-8956(73)90035-X. |
[13] | I. Schiermeyer, All Cycle-Complete Graph Ramsey Numbers r(Cm, K6), J. Graph Theory 44 (2003) 251-260, doi: 10.1002/jgt.10145. |
[14] | Y.J. Sheng, H.Y. Ru and Z.K. Min, The value of the Ramsey number R(Cn,K4) is 3(n−1) +1 (n ≥ 4), Australas. J. Combin. 20 (1999) 205-206. |
[15] | A. Thomason, private communication. |
Received 6 November 2003
Revised 16 February 2005
Close