问题
1-平面图:可画在平面上使每条边至多被交叉一次。Borodin 1984 证明其 6 可着色;猜想 5 足够。下界:存在需 5 色的 1-平面图(构造已知),故问题的答案在 {5, 6} 之间—— «四色的 1-平面延伸» 是 {5 还是 6} 的单比特问题。
主要概念
交叉点的 «局部四点» 结构
1-平面画法中每个交叉点涉及四条 «半边»; «交叉对»(两条互交的边)的端点形成 «虚拟 K₄»—— «局部结构库»:把每个交叉对 «压平» 成 K₄ 边得 «平面骨架 + 虚拟边»;染色的困难在于 «虚拟 K₄» 未必真存在( «交叉对端点间的边可能不存在»),使 «K₄ 缩减» 归约失效。
6-染色的机器
Borodin 的证明走 «极小反例 + 消电(discharging)»:1-平面图的 «平均度 < 6» 型结构引理( «低度点» 密度),加上 «度 ≤ 5 的点邻域可染色» 的情形分析。5-染色的同一机器在 «5 度点的邻域» 处卡住——邻域内的交叉让 «5 邻点不成团» 的平面论证失效。
主要命题与证明
命题 1(Borodin 6-染色定理,完整骨架) 每个 1-平面图 6 可着色。
梗概 极小反例 G:消电给出 «存在度 ≤ 5 的顶点 v 或低度结构»; «1-平面 + 平均度» 分析:交叉把 «边» 变 «半边», «有效边数» ≤ 4n−4 型(比平面 3n−6 松但仍 < 3n),故存在度 ≤ 5 的 «真实度» 点;v 删除后 6-染色可延拓(v 只有 ≤ 5 邻点、6 色有余)。□
命题 2(5 色下界构造) «十字 K₅» 型构造:5 个 «真» 点 + 交叉 «虚拟» 补边——显式 5-色必需的 1-平面图存在( «五色是下界» 立得)。
进展与文献
Borodin 1984(6-染色,与 «1-平面图的清单染色» 系列同源);Czap–Jendrol 的 1-平面图结构综述;Kynčl–... 的 «外 1-平面» 特例(顶点全在凸壳,5-染色已证—— «局部结构受限» 时机器走得通)。开放核心:一般 1-平面图的 5-染色—— «度 ≤ 5 邻域» 的分类爆炸是技术障碍; «弱 1-平面»(每边至多 «重交叉» 约束变体)与 «fan-crossing» 家族的谱系各自半开。