The cycle-complete graph Ramsey number r(C₅,K₇)

Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 129-139
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ingo Schiermeyer. "The cycle-complete graph Ramsey number r(C₅,K₇)." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 129-139. <http://eudml.org/doc/270373>.

@article{IngoSchiermeyer2005,
abstract = {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.},
author = {Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ramsey numbers; extremal graphs},
language = {eng},
number = {1-2},
pages = {129-139},
title = {The cycle-complete graph Ramsey number r(C₅,K₇)},
url = {http://eudml.org/doc/270373},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Ingo Schiermeyer
TI - The cycle-complete graph Ramsey number r(C₅,K₇)
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 129
EP - 139
AB - 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.
LA - eng
KW - Ramsey numbers; extremal graphs
UR - http://eudml.org/doc/270373
ER -

References

top
  1. [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. Zbl0248.05127
  2. [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. Zbl0963.05094
  3. [3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
  4. [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. Zbl0233.05123
  5. [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. Zbl0383.05027
  6. [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. Zbl0294.05122
  7. [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. Zbl0902.05050
  8. [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 Zbl0969.05044
  9. [9] V. Nikiforov, The cycle-complete graph Ramsey numbers, preprint 2003, Univ. of Memphis. Zbl1071.05051
  10. [10] S.P. Radziszowski, Small Ramsey numbers, Elec. J. Combin. 1 (1994) DS1. 
  11. [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. [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. [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. [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. Zbl0931.05057
  15. [15] A. Thomason, private communication. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.