Giả thuyết Erdős–Faber–Lovász

Nếu $G = \bigcup_{i=1}^n A_i$ là hợp của $n$ đồ thị đầy đủ đôi một rời nhau theo cạnh $A_1, \dots, A_n$, mỗi đồ thị có $n$ đỉnh, sao cho $|V(A_i) \cap V(A_j)| \le 1$ với mọi $1 \le i < j \le n$, thì sắc số của $G$ thỏa mãn $\chi(G) = n$ (tương đương, mọi siêu đồ thị tuyến tính trên $n$ đỉnh đều có chỉ số sắc số $\chi'(\mathcal{H}) \le n$).

Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku và Deryk Osthus công bố chứng minh vào tháng 1 năm 2021 (xuất bản trên Annals of Mathematics năm 2023), khẳng định giả thuyết Erdős–Faber–Lovász cho mọi $n \ge n_0$ đủ lớn. Xét một cách chặt chẽ trên toàn bộ các số nguyên $n$, bài toán đã được giải tiệm cận (cho $n \ge n_0$) và được kiểm chứng cho $n \le 12$ (Hindman 1981 cho $n \le 10$; Romero và Alonso-Pecina 2014 cho $n \le 12$), trong khi hữu hạn các giá trị trung gian $13 \le n < n_0$ vẫn còn mở.