Exact value for Ramsey number of \(k\)-cycle and star

For two graphs \( G\) and \( H\), let \( r(G,H)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete graph \( K_m\) are colored in red and blue, then there is either a subgraph isomorphic to \( G\) with all red edges or a subgraph isomorphic to \( H\) with all blue edges. The classical Ramsey numbers are those for the complete graphs and are denoted by \( r(s,t)= r(K_s, K_t)\).

Together with Burr {1], Erdös, Faudree, Rousseau, and Schelp proposed the following problem:

Problem

Determine \(r(C_4,K_{1,n})\).

It is known that

\(\displaystyle n + \lceil \sqrt n \rceil +1 \geq r(C_4,K_{1,n}) \geq n + \sqrt{n}- 6 n^{11/40}, \)

where the upper bound can be easily derived from the Turán number of \( C_4\) and the lower bound can be found in [1]. Füredi shows (unpublished) that \( r(C_4, K_{1,n})= n + \lceil \sqrt n \rceil \) holds infinitely often.

Bibliography
1 S. A. Burr, P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp, Some complete bipartite graph-tree Ramsey numbers, Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), Ann. Discrete Math., 41, 79-89, North-Holland, Amsterdam-New York, 1989.


Footnotes

... Burr1 entht