×

All cycle-complete graph Ramsey numbers \(r(C_{m}, K_{6})\). (English) Zbl 1031.05086

Summary: The cycle-complete graph Ramsey number \(r(C_m, K_n)\) is the smallest integer \(N\) such that every graph \(G\) of order \(N\) contains a cycle \(C_m\) on \(m\) vertices or has independence number \(\alpha (G) \geq n\). It has been conjectured by P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp [J. Graph Theory 2, 53-64 (1978; Zbl 0383.05027)] that \(r(C_m, K_n) = (m - 1) (n - 1) + 1\) for all \(m \geq n \geq 3\) (except \(r(C_3, K_3) = 6\)). This conjecture holds for \(3 \leq n \leq 5\). In this paper we present a proof for \(n = 6\) and for all \(n \geq 7\) with \(m \geq n^2 - 2n\).

MSC:

05C55 Generalized Ramsey theory
05C38 Paths and cycles

Citations:

Zbl 0383.05027
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J Combin Theory Ser B 14 pp 46– (1973)
[2] Bollob?s, J Combin 22 pp 63– (2000)
[3] and Graph Theory with applications, Macmillan, London and Elsevier, New York, 1976.
[4] Chv?tal, Discrete Math 2 pp 111– (1972)
[5] Erd?s, J Graph Theory 2 pp 53– (1978)
[6] Faudree, Discrete Math 8 pp 313– (1974)
[7] Jayawardene, Cong Numerantium 123 pp 97– (1997)
[8] Jayawardene, J Graph Theory 35 pp 99– (2000)
[9] Radziszowski, Elec J Combin 1 pp ds1– (1994)
[10] Radziszowski, J Comb Math Comb Comput 42 pp 195– (2002)
[11] Rosta, J Combin Theory Ser B 15 pp 94– (1973)
[12] The Ramsey number for a cycle of length five versus a complete graph of order seven. Manuscript, May 2001.
[13] Sheng, J Combin 20 pp 205– (1999)
[14] private communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.