Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

Computation of the Ramsey Numbers \(R(C_{4}, K_{9})\) and \(R(C_{4}, K_{10})\)

Alexander Lange1, Ivan Livinskyt2, Stanislaw Radziszowski3
1Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1.
2 Department of Mathematics, University of Toronto, Toronto, ON M5S 2E4.
3Department of Computer Science, Rachester Institute of Technol- ogy, Rochester, NY 14623.
  • Published: 31/05/2016

Abstract

The Ramsey number \( R(C_4, K_m) \) is the smallest \( n \) such that any graph on \( n \) vertices contains a cycle of length four or an independent set of order \( m \). With the help of computer algorithms, we obtain the exact values of the Ramsey numbers \( R(C_4, K_9) = 30 \) and \( R(C_4, K_{10}) = 36 \). New bounds for the next two open cases are also presented.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
Alexander Lange, Ivan Livinskyt, Stanislaw Radziszowski. Computation of the Ramsey Numbers \(R(C_{4}, K_{9})\) and \(R(C_{4}, K_{10})\)[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 097. 139-154. DOI: .