解法: 反復吸収法によるKang–Kelly–Kühn–Methuku–Osthusの漸近的証明(2021年)
ざっくり言うと
もし大きな辺に新しい色パレットを使い、中程度の辺に別のパレット、小さな辺に3つ目のパレットを使ったなら、色の総数は容易に を超えてしまう。その代わりに、各色クラスを層をまたいで再利用しなければならない:最初に大きな超辺や中程度の超辺に割り当てられた色は、後で残りの頂点上の互いに素な小さな辺を付け加えることで拡張される。
課題は、大きな辺や中程度の辺がすでに各色クラス内で頂点の集合を塞いでいるため、小さな辺に対するニブルと吸収の機構が、各色でまだ空いている頂点部分集合の内部で機能しなければならない点である。
詳しい解説
Kang、Kelly、Kühn、Methuku、Osthus(2023年、2.2節および7節)は、各層の彩色をどのように結合するかを説明する。まず第5節で、射影平面スケール 付近またはそれ以上のすべての辺を彩色し、色集合 を持つ部分彩色を作る。次に第6節で、局所的に疎なグラフの彩色を用いて中程度の辺を彩色しつつ、 の色を注意深く再利用し、制御された新しい色 を導入して、 のすべての高次数頂点がこれまでに使われたほぼすべての色クラスで覆われるようにする。
最後に第7節で、レードルのニブル法と予備吸収のマッチング拡張版(ステップ3と4を発展させたもの)によって、これらの既存のマッチング(色クラス)を小辺部分超グラフ へと拡張し、 内の重い頂点が引き続きほぼ完璧な被覆を持ち、残ったサイズ の辺をヴィジングの定理または 因子分解で仕上げられるようにする。
- のほぼ完璧な被覆
- 辺素なマッチングの族 が高次数頂点集合 のほぼ完璧な被覆を持つとは、すべての が少なくとも 個のマッチングで覆われ、各マッチングが見逃す の頂点が高々1つであることをいう。