Problem 19

If $G$ is an edge-disjoint union of $n$ copies of $K_n$ then is $\chi(G)=n$ ?

Graph theory
Chromatic number

Wiki page

Status

Open

No claim settles this problem.

Decidable. The site credits Kang, Kelly, Kühn, Methuku and Osthus [KKKMO21] with the answer yes for all sufficiently large $n$ , an accepted partial claim (claim page (Kang, Kelly, Kühn, Methuku and Osthus, 2021)) that leaves finitely many $n$ unsettled; Hindman [Hi81] settles every $n\le 10$ (claim page (Hindman, 1981)).

Al21: Alesandroni, Guillermo, The Erdős-Faber-Lovász conjecture for weakly dense hypergraphs. Discrete Math. 344(7) (2021), Paper No. 112401, 7.
ArVa16: Araujo-Pardo, G. and Vázquez-Ávila, A., A note on Erdös-Faber-Lovász conjecture and edge coloring of complete graphs. Ars Combin. (2016), 287-298.
Er78: Erdős, Paul, Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) (1978), 29-40.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter IV, pp. 341--342 states the conjecture in the edge-disjoint form ("if $G$ is the edge disjoint union of $n$ complete graphs of size $n$ then $G$ has chromatic number $n$ "), the prize offer, Kahn's bound "less than $(1+o(1))n$ " with a consolation prize, and the Füredi--Erdős generalization to $n$ complete graphs of size $n$ pairwise sharing at most $k$ vertices, conjectured to have chromatic number at most $kn$ , without proof. Library home: Erdős 1993.
Er97d: Erdős, Paul, Some recent problems and results in graph theory. Discrete Math. 164 (1997), 81--85; item 1, p. 81 states the conjecture in the edge-disjoint-cliques form, the prize offer and Kahn's bound $\le n(1+o(1))$ without proof. Library home: Erdős 1997.
Hi81: Hindman, Neil, On a conjecture of Erdős, Faber, and Lovász about $n$ -colorings. Canadian J. Math. (1981), 563-570.
HoTu90: Horák, Peter and Tuza, Z., A coloring problem related to the Erd\H os-Faber-Lovász conjecture. J. Combin. Theory Ser. B (1990), 321-322.
KKKMO21: Kang, D. Y. and Kelly, T. and Kühn, D. and Methuku, A. and Osthus, D., A proof of the Erdős-Faber-Lovász conjecture. arXiv:2101.04698 (2021).
KKKMO24: Kang, Dong Yeap and Kelly, Tom and Kühn, Daniela and Methuku, Abhishek and Osthus, Deryk, Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree. Proc. Lond. Math. Soc. (3) (2024), Paper No. e70011, 32.
Ka92: Kahn, Jeff, Coloring nearly-disjoint hypergraphs with $n+o(n)$ colors. J. Combin. Theory Ser. A (1992), 31-39.
RoSa07: Romero, David and Sánchez-Arroyo, Abdón, Adding evidence to the Erdős-Faber-Lovász conjecture. Ars Combin. (2007), 71-84.

Problem 19

Status

Proof claims

Discussion