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

Kang、Kelly、Kuhn、Methuku、Osthus(2023年、2.1節)は、辺のサイズが有界 $2 \le |e| \le r$ な場合の議論を概説する。$G$ を $\mathcal{H}$ のサイズ $2$ の辺からなるグラフとする。$G$ の各辺を確率 $1/2$ で独立にランダムな予備 $R$ に入れる。高確率ですべての頂点が小さな $\xi$ に対して $d_R(v) = d_G(v)/2 \pm \xi n$ を満たすので、$\Delta(\mathcal{H}\setminus R) \le (1/2+\xi)n$ となり、ピッペンジャー・スペンサーの定理により $\chi'(\mathcal{H}\setminus R) \le (1/2+\gamma)n$ が得られる。レードルのニブル法を $\mathcal{H}\setminus R$ に反復適用して、ほぼ全次数の頂点集合 $U$ を「ほぼ完璧に」覆う大きなマッチングを構築し、各マッチングが見逃す(高々1つの)頂点を $R$ の辺で修復する。残ったわずかな未彩色の辺は、これまでに使った色集合 $C$ に対し最大次数が高々 $n-|C|$ なので、ヴィジングの定理により $\chi'(\mathcal{H}\setminus\mathcal{H}') \le \Delta(\mathcal{H}\setminus\mathcal{H}')+1$ が得られ、合わせて $\chi'(\mathcal{H}) \le n+1$ となる。