On anti-Ramsey numbers for complete bipartite graphs and the Turan function

Abstract: Given two graphs

G

and

H

with

H s u b s e t e q G

we consider the anti-Ramsey function

A R (G, H)

which is the maximum number of colors in any edge-coloring of

G

so that every copy of

H

receives the same color on at least one pair of edges. The classical Tur'an function for a graph

G

and family of graphs

m a t h c a l F

, written

e x (G, m a t h c a l F)

, is defined as the maximum number of edges of a subgraph of

G

not containing any member of

m a t h c a l F

. We show that there exists a constant

c > 0

so that

A R (K_{n}, K_{s, t}) - e x (K_{n}, K_{s, t}) < c n

and

c

depends only on

s

and

t

, which implies

A R (K_{n}, K_{s, t}) l e q c n^{2 - f r a c 1 s}

, for

s l e q t

by a result of KH ovari, S'os, and Tur'an.

This page was built for publication: On anti-Ramsey numbers for complete bipartite graphs and the Turan function