The cycle-complete graph Ramsey number \(r(C_5, K_7)\). (English) Zbl 1074.05063

The Ramsey number \(r(G,H)\) of graphs \(G\) and \(H\) is the smallest natural number \(N\) such that any red-blue colouring of the edges of \(K_N\) yields either a red \(G\) or a blue \(H\). In the case where \(G\) is a cycle and \(H\) a complete graph, this is known as the cycle-complete graph Ramsey number. The graph \((n-1)K_{m-1}\) shows that \(r(C_m, K_n)\geq (m-1)(n-1)+1\) for all \(m\geq n\geq 3\). It has been conjectured that, except for \(r(C_3,K_3)=6\), equality holds in the above formula. A more challenging conjecture, due to V. Nikiforov [Comb. Probab. Comput. 14, 349–370 (2005; Zbl 1071.05051)], is that for every \(k\) there exists \(n_0=n_0(k)\) such that for \(n>n_0(k)\) and \(m>n^{1/k}\), \(r(C_m,K_n)=(m-1)(n-1)+1\). In this paper it is proved that \(r(C_5,K_7)=25\), which, with the results known for \(m=5\), \(n<7\), suggests that the formula may hold for all \(m\geq 5\).


05C55 Generalized Ramsey theory
05C35 Extremal problems in graph theory


extremal graphs


Zbl 1071.05051
Full Text: DOI