On a Coloring Problem of P. Erdés

Abstract

Let $f(n,k)$ be the maximum chromatic number among all graphs whose edge set can be covered by $n$ copies of $K(n)$, the complete graph on $n$ vertices, so that any two of those $K(n)$ share at most $k$ vertices.It has been known that $f(n,k)=(1–o(1)).n^{3/2}$ for $k\ge n^{1/2}$. We show that
$(1–o(1))n.k\le f(n,k)\le (k+1)(n-k)$ for $k<n^{1/2}$, hence, for $1/k=o(1)$,$f(n,k)=(1+o(1))n.k.$