On Edge Colorings with at Least q Colors in Every Subset of p
Vertices  Gábor N. Sárközy, Stanley Selkow   For fixed integers
$p$ and $q$, an edge coloring of $K_n$ is called a $(p,
q)$-coloring if the edges of $K_n$ in every subset of $p$
vertices are colored with at least $q$ distinct colors. Let
$f(n, p, q)$ be the smallest number of colors needed for a $(p,
q)$-coloring of $K_n$. In [3] Erdős and Gyárfás studied this
function if $p$ and $q$ are fixed and $n$ tends to infinity.
They determined for every $p$ the smallest $q$ ($= {p \choose 2}
- p + 3$) for which $f(n,p,q)$ is linear in $n$ and the smallest
$q$ for which $f(n,p,q)$ is quadratic in $n$. They raised the
question whether perhaps this is the only $q$ value which
results in a linear $f(n,p,q)$. In this paper we study the
behavior of $f(n,p,q)$ between the linear and quadratic orders
of magnitude. In particular we show that that we can have at
most $\log p$ values of $q$ which give a linear $f(n,p,q)$.
Full Text: PDF