pith. sign in

arxiv: 1108.5204 · v2 · pith:6MCRYTU3new · submitted 2011-08-25 · 🧮 math.CO

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

classification 🧮 math.CO
keywords functiongraphsmathcalanti-ramseyedgesmaximumnumberbipartite
0
0 comments X
read the original abstract

Given two graphs $G$ and $H$ with $H\subseteq G$ we consider the anti-Ramsey function $AR(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 $\mathcal{F}$, written $ex(G,\mathcal{F})$, is defined as the maximum number of edges of a subgraph of $G$ not containing any member of $\mathcal{F}$. We show that there exists a constant $c>0$ so that $AR(K_n,K_{s,t})-ex(K_n,K_{s,t})<cn$ and $c$ depends only on $s$ and $t$, which implies $AR(K_n,K_{s,t})\leq cn^{2-\frac{1}{s}}$, for $s\leq t$ by a result of K\H ovari, S\'os, and Tur\'an.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.