解法：康–凯利–库恩–梅苏库–奥斯图斯基于迭代吸收法的渐近证明(2021年)

第 6/8 步：不浪费颜色地将各层缝合在一起

通俗地说

如果给大边用一套全新的颜色、给中边用另一套颜色、再给小边用第三套颜色,颜色总数很容易超过 $n$ 。因此,每个颜色类都必须跨层复用:先分配给大超边或中超边的同一种颜色,之后还要在剩余顶点上添入互不相交的小边加以扩充。

难点在于,大边和中边已经在每个颜色类内部占据了一部分顶点,因此针对小边的蚕食与吸收机制必须在每种颜色中仍然空闲的顶点子集内部运作。

\mathcal{H}_1 \supseteq \mathcal{H}_{\text{large}},\quad \chi'(\mathcal{H}_1) \le |C_1|,\quad \text{extend colour classes via Rödl nibble to } \mathcal{H}_{\text{small}}

详细分析

Kang、Kelly、Kühn、Methuku 与 Osthus(2023年,第2.2节与第7节)阐述了如何将各层的染色结合起来。首先,第5节对射影平面尺度 $\sqrt{n}$ 附近或之上的所有边进行染色,得到使用颜色集 $C_1$ 的部分染色。接着,第6节利用局部稀疏图染色给中等边染色,同时谨慎地复用 $C_1$ 中的颜色并引入受控的新颜色集 $C_2$ ,确保 $\mathcal{H}$ 的每个高度数顶点都被目前已使用的几乎所有颜色类覆盖。

最后,第7节通过罗德尔蚕食法与储备吸收的匹配扩充版本(在第3步和第4步基础上发展而来),将这些已有的匹配(颜色类)扩充到小边子超图 $\mathcal{H}_{\text{small}}$ 中,使 $U$ 中的重顶点继续保持近乎完美的覆盖,从而剩余的大小为 $2$ 的边仍可用维京定理或 $1$ -因子化完成染色。

本步骤中的术语

对 $U$ 的近乎完美覆盖: 一组边不相交的匹配族 $\mathcal{N}$ 对高度数顶点集 $U$ 具有近乎完美覆盖,是指每个 $u \in U$ 至少被 $|\mathcal{N}|-1$ 个匹配覆盖,且每个匹配至多遗漏 $U$ 中的一个顶点。

本步骤用到的知识

图着色与四色定理概率方法