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

Abstract: Harary's conjecture

r (C_{3}, G) l e q 2 q + 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 g e q 2

, we will show that

r (C_{4}, G) l e q k q + 1

and that equality holds if

G c o n g 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 g e q 2

edges and with no isolated vertices,

r (C_{4}, G) l e q 2 p + q - 2

where

p = | V (G) |

and that equality holds if

G c o n g K_{3}

.

This page was built for publication: How Ramsey theory can be used to solve Harary's problem for $K_{2,k}$