エルデシュ・フェイバー・ロヴァース予想

$G = \bigcup_{i=1}^n A_i$ が、それぞれ $n$ 個の頂点をもち任意の $1 \le i < j \le n$ に対して $|V(A_i) \cap V(A_j)| \le 1$ を満たす $n$ 個の完全グラフ $A_1, \dots, A_n$ の和であるならば、$G$ の染色数は $\chi(G) = n$ を満たす（同値な表現として、$n$ 頂点上の任意の線形ハイパーグラフの辺染色数は $\chi'(\mathcal{H}) \le n$ である）。

カン・ドンヨプ（Dong Yeap Kang）、トム・ケリー、ダニエラ・キューン、アビシェク・メトゥク、デレク・オストフスは2021年1月に証明を発表し（2023年に Annals of Mathematics に掲載）、十分大きなすべての $n \ge n_0$ に対してエルデシュ・フェイバー・ロヴァース予想を確立した。すべての整数 $n$ にわたる厳密な状況としては、漸近的領域（$n \ge n_0$）で解決され、かつ $n \le 12$ で検証済み（$n \le 10$ は1981年のハインドマン、$n \le 12$ は2014年のロメロとアロンソ＝ペシナ）である一方、有限個の中間領域 $13 \le n < n_0$ は未解決として残されている。