How Ramsey theory can be used to solve Harary's problem for $K_{2,k}$

Abstract

Harary's conjecture $r(C_3,G)\le 2q+1$ for every isolated-free graph G with $q$ edges was proved independently by Sidorenko and Goddard and Klietman. In this paper instead of $C_3$ we consider $K_{2,k}$ and seek a sharp upper bound for $r(K_{2,k},G)$ over all graphs $G$ with $q$ edges. More specifically if $q\ge 2$, we will show that $r(C_4,G)\le kq+1$ and that equality holds if $G\cong q{K}_2$ or $K_3$. Using this we will generalize this result for $r(K_{2,k},G)$ when $k>2$. We will also show that for every graph $G$ with $q\ge 2$ edges and with no isolated vertices, $r(C_4,G)\le 2p+q-2$ where $p=|V(G)|$ and that equality holds if $G\cong K_3$.

8 pages, 4 figures