问题
平方图 G²:V(G) 相同,«距离 ≤ 2» 连边。χ(G²) ≤ f(Δ)。Wegner 1977 猜想 f(Δ) ≤ Δ + 4(平面);Δ = 3 的反例(7 色需求,Molloy–Salavatian 型构造)终结原文;修正版 «Δ+5»(Δ = 3 时 7 = 3+4 恰好 «贴边»)与 «Δ+O(1)» 的一般版都开放。当前最好:χ(G²) ≤ Δ + O(Δ2/3log Δ)(平面)、≤ 1.66Δ3/2 + o(一般图,Molloy–Reed)。
主要概念
平方图的 «局部密度»
«距离-2 邻居数»:平面图中顶点 v 的平方度 ≤ 3Δ² 级(«度-Δ «邻居的邻居»»)—— «贪婪上界» Δ² + 1;«低度 «区域»» 的 «结构» 决定 «真实» 上界。Wegner 猜想的直觉:平面图的 «低密度» 使 «距离-2 邻居» 仅 «O(Δ)» 级。
「贪婪 + 修补」机器
«颜色 «阵列»»:«每点 «排除 «距离-2» 冲突»» 后 «剩余颜色 ≥ 1» 的 «贪婪» 需 «色数 ≥ 最大平方度 + 1 ~ 3Δ²»—— «修补»(«局部重排»、«Kempe»)把 «Δ² » 压到 «Δ + O(Δ^{2/3})»: «低度 «中心»» 的 «修补自由度»。
主要命题与证明
命题 1(Δ=3 的 7 色反例,完整陈述) 存在 Δ = 3 平面图 χ(G²) = 7(Wegner 的 «立方 «蜂窝»» 型构造)—— «Δ+4 = 7 恰好成立» 的 «贴边»,但 «Δ+3 = 6» 被反例排除:构造 «立方平面图» 使 «距离-2 邻居 = 全图»(直径 2 的立方平面图),χ(G²) = χ(G) + «结构» = 7 级。
展开(构造核) «Moser «纺锤»» 型 «立方 «蜂窝»»:«每个 «面»» 的 «中心点» 与 «环» 相连—— «环上的 «距离-2»» 恰是 «面中心» 的 «邻域»—— «平方图 = «面图 + 环图»» 的 «7-色需求»。«7 = Δ+4» 的 «贴边» 使 «Wegner 原文 » 对 Δ = 3 «恰好正确»,«Δ+3» 错。□
命题 2(Δ + O(Δ^{2/3}log Δ) 上界,完整骨架) 平面图 χ(G²) ≤ Δ + C·Δ2/3log Δ(Bonamy–Charpentier–… 2018 系)。
骨架 ①«分解»:«低度 «核心»»(«度 ≤ Δ/2» 的 «大 «部分»»)与 «高度 «边缘»»;②«核心 «贪婪»»:«平方度 ≤ Δ + C·Δ^{2/3}log Δ» 的 « «局部 «计数»»»(« «距离-2» «邻居» 的 «密集 «区域»» 被平面性压制—— « «密集 » 区域的 «欧拉» 上界»);③«边缘 «修补»»:«高度点的 «局部 Kempe»»—— «Δ^{2/3}» 是 « «区域 «半径»» 与 «计数» 的平衡指数。□
命题 3(一般图的 1.66Δ^{3/2},完整骨架) 任意图 χ(G²) ≤ 1.66Δ3/2 + o(Δ3/2)(Molloy–Reed 2001;Alon–Mohar 的下界 Ω(Δ²/log²Δ) 的 «随机 » 对偶)—— «一般图 » 与 «平面 » 的 «间隙 » 是 «Wegner» 的 «平面性 » 价值。□
进展与文献
Wegner 1977;Molloy–Salavatian 的反例;Molloy–Reed 的平方染色机器;Bonamy–Perrett 的 «Δ+O(Δ^{2/3})» 系(2016+)。开放核心:Δ+O(1)(平面);«Δ+5» 的修正版;«Δ = 3 的 «精确 7»» 与 «Δ = 4 的 «精确 »»—— «小 Δ» 的 «精确函数表 »。