九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

1-平面图的染色数

《图论中的 50 个公开问题》 · 问题 36 专题综述

题面每条边至多交叉一次的图(1-平面图)是否都 5 可着色?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

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» 家族的谱系各自半开。

← 返回问题 36