解法: 反復吸収法によるKang–Kelly–Kühn–Methuku–Osthusの漸近的証明(2021年)

Kang、Kelly、Kuhn、Methuku、Osthus(2023年、序論)は、1972年にエルデシュ、ファーバー、ロヴァースが3つの同値な主張を予想したことを振り返る(1.1節参照)。そのうちグラフ理論的な読み方は:グラフ $G$ が $n$ 個のクリーク(それぞれ大きさ高々 $n$)の和集合であり、どの2つのクリークも高々1つの頂点を共有するなら、$G$ の彩色数は高々 $n$ である、というものである。論文全体を通して用いられる同値な超グラフ彩色の定式化は:$n$ 個の頂点を持つ線形超グラフ $\mathcal{H}$(任意の2つの辺が高々1つの頂点を共有するもの)について、彩色指数 $\chi'(\mathcal{H})$(交わる辺が異なる色を持つように超辺を彩色するのに必要な最小色数)が $\chi'(\mathcal{H}) \le n$ を満たす、というものである。エルデシュはこれを自身の3つのお気に入りの組合せ問題の1つと呼び、その難しさが明らかになるにつれ懸賞金を引き上げ、最終的に500ドルに達した。