Publication Date:
2014-12-27
Description:
Fix positive integers $p$ and $q$ with $2 \leq q \leq {p \choose 2}$ . An edge coloring of the complete graph $K_n$ is said to be a $(p, q)$ -coloring if every $K_p$ receives at least $q$ different colors. The function $f(n, p, q)$ is the minimum number of colors that are needed for $K_n$ to have a $(p,q)$ -coloring. This function was introduced about 40 years ago, but Erdős and Gyárfás were the first to study the function in a systematic way. They proved that $f(n, p, p)$ is polynomial in $n$ and asked to determine the maximum $q$ , depending on $p$ , for which $f(n,p,q)$ is subpolynomial in $n$ . We prove that the answer is $p-1$ .
Print ISSN:
0024-6115
Electronic ISSN:
1460-244X
Topics:
Mathematics
Permalink