Problem #19: If $G$ is an edge-disjoint union of $n$ copies of $K_n$...

---

Progress

Conjectured by Erdős, Faber, and Lovász (apparently 'at a party in Boulder, Colarado in September 1972' [Er81]).

Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$ (for which Erdős gave him a 'consolation prize' of \$100). Hindman [Hi81] proved the conjecture for $n<10$. Various special cases have been established by Romero and Sáchez-Arroyo [RoSa07], Araujo-Pardo and Vázquez-\'{A}vila [ArVa16], and Alesandroi [Al21].

Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO21] have proved the answer is yes for all sufficiently large $n$.

In [Er97d] Erdős asks how large $\chi(G)$ can be if instead of asking for the copies of $K_n$ to be edge disjoint we only ask for their intersections to be triangle free, or to contain at most one edge.

In [Er93] Erdős and Füredi conjecture the generalisation that if $G$ is the union of $n$ copies of $K_n$, which pairwise intersect in at most $k$ vertices, then $\chi(G)\leq kn$. This has been proved for all sufficiently large $n$ (not depending on $k$) by Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO24]. Furthermore, Horák and Tuza [HoTu90] proved that if $\chi(G) \leq n^{3/2}$ if $G$ is the union of $n$ copies of $K_n$, and hence this conjecture also holds whenever $k<\sqrt{n}$.