Computation of the Ramsey numbers R(C₄,K₉) and R(C₄,K₁₀)

MaRDI QIDQ2829342zbMATH OpenFDO

Authors Alexander Lange, Ivan Livinsky, Stanisław P. Radziszowski

Publication date 27 October 2016

Published in JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.3017

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

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.

Review text

The cycle-complete Ramsey number \(R(C_n, K_m)\) is the minimal natural number \(N\) such that, for any (red/blue)-coloring of the edges of the complete graph \(K_N\), there is either red copy of the cycle \(C_n\) or blue copy of \(K_m\).NEWLINENEWLINEThe author's computer obtained: NEWLINE\[NEWLINER(C_4, K_g)=30,\quad R(C_4,K_{10})=36,NEWLINE\]NEWLINE NEWLINE\[NEWLINE39\leq R(C_4,K_{11})\leq 44,\quad 42\leq R(C_4, K_{12})\leq 52.NEWLINE\]NEWLINE Some speculative remarks after the references must ensure the reader to trust in the computer.NEWLINENEWLINEFor recent hand-made progress in computation of \(R(K_2^n,K_m)\) see [\textit{G. Fiz Pontiveros} et al., J. Lond. Math. Soc., II. Ser. 89, No. 3, 680--702 (2014; Zbl 1295.05253)].

Recommendations

• Computation of Ramsey numbers R(C_m,W_n)
• The value of the Ramsey number \(R_4(C_4)\)
• scientific article; zbMATH DE number 1933057
• Ramsey numbers based on \(C_ 5\)-decompositions
• Ramsey numbers for unions of some cycles

Cited in

(6)

• Ramsey numbers based on \(C_ 5\)-decompositions
• Computation of Ramsey numbers R(C_m,W_n)
• scientific article; zbMATH DE number 3882465 (Why is no real title available?)
• A note on the Ramsey numbers R(C₄,B_n)
• scientific article; zbMATH DE number 1874380 (Why is no real title available?)
• Some upper bounds on Ramsey numbers involving C₄

This page was built for publication: Computation of the Ramsey numbers \(R(C_4,K_9)\) and \(R(C_4,K_{10})\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829342)