Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 19

claims/: The 5 claim pages of Problem 19, one per claimant's result; the problem's standing derives from them.

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

Status. 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 ([[problems/graph_coloring/E0019/claims/2021_01_12_kang_kelly_kuhn_methuku_osthus|claim page]]) that leaves finitely many $n$ unsettled; Hindman [Hi81] settles every $n\le 10$ ([[problems/graph_coloring/E0019/claims/1981_06_01_hindman|claim page]]).

Source. erdosproblems.com/19, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #19, https://www.erdosproblems.com/19.

References.

[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: erdos_1993_my_favorite_solved_unsolved_problems_graph_theory.
[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: erdos_1997_some_recent_problems_results_graph_theory.
[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.

Formalization. Statement in formal-conjectures, added on 2026-09-27, after the site access; the statement and the variants it lists for $n<10$ , Kahn's bound and the large- $n$ result are left unproved there, only the case $n\le 3$ is proved, and it names no formal proof. A Lean 4 development of the large- $n$ theorem, Erdos19.lean in Boris Alexeev's lean-proofs collection (added 2026-08-26), is linked from the [[problems/graph_coloring/E0019/claims/2021_01_12_kang_kelly_kuhn_methuku_osthus|claim page]]; this corpus has not built it.

Current assessment

The question, in the site's formulation accessed, asks whether an edge-disjoint union of $n$ copies of $K_n$ always has chromatic number $n$ , the conjecture of Erdős, Faber and Lovász from 1972. The standing is open with no full claim, and every claim page is an accepted partial claim. The principal one is [[problems/graph_coloring/E0019/claims/2021_01_12_kang_kelly_kuhn_methuku_osthus|Kang, Kelly, Kühn, Methuku and Osthus's proof for large $n$ ]], refereed in Ann. of Math. (2) 198 (2023), which proves the answer yes for all $n\ge n_0$ with a threshold $n_0$ the paper does not compute (card). The problem is thereby reduced to finitely many values of $n$ , which the site's label decidable records; no published argument bounds $n_0$ , so the remaining check is finite but of unspecified size. Hindman [Hi81] settles every $n\le 10$ through a reduction to small intersection families and a computer check, an accepted partial claim (claim page); the site's remark gives the range as $n<10$ . Kahn [Ka92] proved $\chi(G)\le(1+o(1))n$ , a bound that settles the question for no configuration, so it has no claim page. Special classes of configurations are accepted partial claims: [[problems/graph_coloring/E0019/claims/2007_01_01_romero_sanchez_arroyo|edge-conformable configurations]] [RoSa07], [[problems/graph_coloring/E0019/claims/2016_05_11_araujo_pardo_vazquez_avila|arithmetic decompositions with different central vertices]] [ArVa16] and [[problems/graph_coloring/E0019/claims/2020_10_12_alesandroni|weakly dense configurations]] [Al21]. The generalization of Erdős and Füredi in [Er93], that $n$ copies of $K_n$ pairwise sharing at most $k$ vertices have chromatic number at most $kn$ , was proved for every $k\ge2$ and all sufficiently large $n$ by the same authors [KKKMO24] (Theorem 1.2), with one threshold for every $k\ge2$ ; the case $k=1$ is their earlier large- $n$ theorem above, which Theorem 1.2 does not imply. Horák and Tuza [HoTu90] proved $\chi(G)\le n^{3/2}$ for any union of $n$ copies of $K_n$ ; these results concern the generalization, not the exact question. The formal-conjectures statement file leaves the question and its variants for $n<10$ , Kahn's bound and the large- $n$ result unproved, proves only the case $n\le 3$ , and names no formal proof; the community database records a formalized statement since 2026-09-27. Boris Alexeev's lean-proofs collection has held a Lean 4 development of the large- $n$ theorem since 2026-08-26. It is linked from the claim page as a formalization of that result. This corpus has not built it, so it gives no formalized evidence.

Search scope, 2026-10-07: the site's problem page (last edited 7 March 2026, no proof claims filed), the arXiv record of arXiv:2101.04698, the Crossref record and the journal's page of the Annals publication, the preprint's card, the arXiv records of arXiv:2010.05666 [Al21] and arXiv:1605.03374 [ArVa16], the zbMATH records Zbl 1224.05187 [RoSa07] and Zbl 1413.05098 [ArVa16], the formal-conjectures statement file, and Boris Alexeev's lean-proofs collection.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (38)

Edge-conformable configurations Arithmetic decompositions with different central vertices Alesandroni proves the conjecture for weakly dense hypergraphs Kang, Kelly, Kühn, Methuku and Osthus prove the conjecture for large n problems/graph_coloring/E0019/claims Graph Coloring extremal_graph_theory/erdos_1978_problems_results_combinatorial_analysis_combinatorial_number extremal_graph_theory/erdos_1993_my_favorite_solved_unsolved_problems_graph_theory Graph Coloring graph_coloring/alesandroni_2021_erdos_faber_lovasz_conjecture_weakly Definition 3.6 (p. 5): weakly dense hypergraphs Theorem 3.5 (p. 4): a linear hypergraph with at most n edges of at most n vertices and minimum degree at least sqrt(n) is n-colorable Theorem 3.7 (p. 5): the Erdős-Faber-Lovász conjecture holds for weakly dense hypergraphs graph_coloring/araujopardo_2016_note_erdos_faber_lovasz Corollary 1.1 (p. 10): an edge arithmetic n-quasicluster whose edges each hold at most one vertex of odd degree has chromatic number at most n Theorem 1.2 (p. 7): an arithmetic decomposition of K_n with different central vertices has chromatic index at most n Theorem 1.3 (p. 10): an edge arithmetic n-quasicluster with different central edges has chromatic number at most n graph_coloring/erdos_1979_problems_results_graph_theory_combinatorial_analysis Conjecture (p. 161): the Erdős--Faber--Lovász conjecture graph_coloring/hindman_1981_conjecture_erdos_faber_lovasz_n_colorings Corollary 2.6 (p. 567): for each n, a finite computation decides whether every small intersection family with |union L(A)| <= n can be colored Corollary 3.3 (p. 569) and the computer check: a split-colorable copy of C(L(A)) makes A colorable, which holds whenever |union L(A)| <= 10 Theorem 2.5 (p. 567): if the completions C(A,m) can be colored for n <= m <= 2n-1 (n odd) or n <= m <= 2n+1 (n even), they can be colored for all m >= n Theorem 3.2 (p. 569): a split coloring of C(A,n) yields a split coloring of C(A,n+1)Jensen–Toft: 25 Pretty graph colouring problems Problem 4 (p. 167): the Erdős–Faber–Lovász question graph_coloring/kang_2021_proof_erdos_faber_lovasz_conjecture Theorem 1.1 (p. 1): for every sufficiently large n, every linear hypergraph on n vertices has chromatic index at most n Theorem 1.2 (p. 2): a large linear hypergraph far from a projective plane, with maximum degree at most (1-δ)n, has chromatic index at most (1-σ)n Theorem 1.3 (p. 2): a large linear hypergraph with maximum degree at most ηn and no edge of size strictly between η√n and √n/η has chromatic index at most εn graph_coloring/kang_2024_solution_problem_erdos_chromatic_index_hypergraphs Corollary 1.4 (p. 3): n complete graphs on at most (1-eps)tn vertices, pairwise sharing at most t vertices, have union of list chromatic number at most tn Theorem 1.2 (p. 2): n complete graphs on at most n vertices, pairwise sharing at most t >= 2 vertices, have union of chromatic number at most tn for n >= n_0 Theorem 1.3 (p. 3): an n-vertex hypergraph with maximum degree at most (1-eps)tn and codegree at most t has list chromatic index at most tn ramsey_theory/erdos_1975_problems_results_finite_infinite_graphs Conjecture (Section X, p. 191): the Faber–Lovász–Erdős conjecture on n sets of size n meeting in at most one element ramsey_theory/erdos_1997_some_recent_problems_results_graph_theory set_systems/erdos_1981_combinatorial_problems_which_i_would_most

Graph