Geodesic
The cycle-complete graph Ramsey number r(C₅,K₇)
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 129-139.

Voir la notice de l'article provenant de la source Library of Science

The cycle-complete graph Ramsey number r(Cₘ,Kₙ) is the smallest integer N such that every graph G of order N contains a cycle Cₘ on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erdős, Faudree, Rousseau and Schelp that r(Cₘ,Kₙ) = (m-1)(n-1)+1 for all m ≥ n ≥ 3 (except r(C₃,K₃) = 6). This conjecture holds for 3 ≤ n ≤ 6. In this paper we will present a proof for r(C₅,K₇) = 25.
Keywords: Ramsey numbers, extremal graphs 
@article{DMGT_2005_25_1-2_a13,
     author = {Schiermeyer, Ingo},
     title = {The cycle-complete graph {Ramsey} number {r(C₅,K₇)}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {129--139},
     publisher = {mathdoc},
     volume = {25},
     number = {1-2},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a13/}
}
TY  - JOUR
AU  - Schiermeyer, Ingo
TI  - The cycle-complete graph Ramsey number r(C₅,K₇)
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 129
EP  - 139
VL  - 25
IS  - 1-2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a13/
LA  - en
ID  - DMGT_2005_25_1-2_a13
ER  - 
%0 Journal Article
%A Schiermeyer, Ingo
%T The cycle-complete graph Ramsey number r(C₅,K₇)
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 129-139
%V 25
%N 1-2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a13/
%G en
%F DMGT_2005_25_1-2_a13
Schiermeyer, Ingo. The cycle-complete graph Ramsey number r(C₅,K₇). Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 129-139. http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a13/

[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:299::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(C₄,Kₙ), 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(Cₘ, K₆), 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(Cₙ,K₄) is 3(n-1) +1 (n ≥ 4), Australas. J. Combin. 20 (1999) 205-206.

[15] A. Thomason, private communication.