解法:康–凯利–库恩–梅苏库–奥斯图斯基于迭代吸收法的渐近证明(2021年)
第 3/8 步:热身:通过随机顶点吸收器达到 n+1 种颜色 通俗地说先关注更简单的情形,即每条超边大小都有界(比如至多 r 个顶点),这使得 H 的大部分变成一个普通图 G(边大小为 2)。思路是随机地把 G 一半的边留作灵活的“储备”,用蚕食法高效地给其余部分染色,再用储备来修补少数(尤其是度数非常高、接近 n 的)顶点,而这些顶点单靠蚕食法无法完美覆盖。
详细分析Kang、Kelly、Kühn、Methuku 与 Osthus(2023年,2.1节)概述了边大小有界 2≤∣e∣≤r 情形的论证。设 G 为 H 中大小为 2 的边构成的图。以概率 1/2 独立地把 G 的每条边放入随机储备 R;高概率下每个顶点都满足 dR(v)=dG(v)/2±ξn(某个小的 ξ),从而 Δ(H∖R)≤(1/2+ξ)n,由皮彭杰–斯宾塞定理得 χ′(H∖R)≤(1/2+γ)n。对 H∖R 迭代应用罗德尔蚕食法,构造出“近乎完美地”覆盖近满度顶点集 U 的大匹配,用 R 中的边修补每个匹配遗漏的(至多一个)顶点;剩下极少数未染色的边,相对于目前已用颜色集 C,最大度数至多为 n−∣C∣,于是维京定理给出 χ′(H∖H′)≤Δ(H∖H′)+1,总计得到 χ′(H)≤n+1。
本步骤中的术语- 维京定理
- 对任意最大度数为 Δ 的普通图 G,其色指数至多为 Δ+1;此处用作对剩余小图的廉价最终修补。
- 顶点吸收器
- 预先保留的一组随机边(此处为储备 R),专门留待之后用来修正先前随机构造未能完美处理的少数顶点。
本步骤用到的知识