On a coloring problem of P. Erdés

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 \geq n^{{1}/{2}}\). We show that
\[(1 – o(1))n.k \leq f(n,k) \leq (k+1)(n-k)\]
for \(k < n^{{1}/{2}}\), hence, for \({1}/{k} = o(1)\), \[f(n,k) = (1 + o(1))n.k.\]