问题
平面图 4-可选(4-choosable):每个平面图在任何 «每顶点 4-列表» 下可正常染色。四色定理保证 «统一 4 色» 的染色;列表版允许 «每点不同的 4 色»——强得多。已知:平面图 5-可选(Thomassen 1994,经典);4-可选开放(1994 至今);反例存在 «5-列表不可染» 平面图(Voigt 1993、Gutner)—— «5 即墙»,4 是分水岭。
主要概念
Thomassen 的 «柱面» 机器
5-可选的证明:«预着色面圈» + «向外扩展»—— «柱面引理»:«面圈 C 上 «预色 ≤ 2 点»» 的 «5-列表» 情形 «无限扩展»;4-可选的失败在于 «4-列表» 使 «柱面引理» 的 «容量条件» 破坏(«每层自由度 4−2 = 2» 太紧)。
DP-染色的 «墙» 现象学
DP-色数(Dvořák–Postle):平面图的 DP-色数 ≤ 5(同列表);«平面图 DP-4 染色» 被证伪——存在 «DP-4 不可染» 平面图(Bernshteyn–Kostochka–Pron 2017)—— «DP ≥ 列表»,DP 反例不直接给列表反例,但 «现象学»(«4 即墙»)在 DP 世界更尖锐。
主要命题与证明
命题 1(Thomassen 5-可选,完整骨架) 平面图 5-可选。
骨架 ①«双柱» 引理:平面图有 «2-面 «耳»» 或 «低度 «柱»»;②«扩展»:«外圈预色» + «内层递归»—— «每层 «耳»» 的 «4-列表剩余» 由 «度 ≥ 5−2 = 3» 的 «贪婪» 覆盖;③«5 的临界»:«4-临界» 结构的 «放电» 保证 «耳» 存在。□
命题 2(«4 即墙» 的反例家族,完整陈述) 存在 «列表 5-不可染» 平面图(Voigt 1993;Gutner 1996 的 «更小» 构造)—— «列表 4-可选 » 的反例若存在需 «更精» 的 «局部结构»(«每个 «4-列表» 不可染» 的 «全局» 构造在 «DP» 世界已有,在 «列表» 世界未造出)。
展开(DP 反例的构造,骨架) «DP-4 反例»:取 «5-临界» 图(如 «四色临界» 的 «皮特森 — 面» 拼装),«对应关系» 设 «成对 «互斥»» 使 «4-列表» 的 «匹配» 强制 «冲突»—— «DP 的 «匹配自由度»» 比 «列表» 大,反例 «容易»;«列表» 世界 «匹配自由度 = 0»,反例构造 «难»。□
命题 3(部分类已证 4-可选,完整清单) ①三角剖分 «无 «4-环»» 的 «3-可选»(部分);②«无 «环长 ≤ 5»» 的 «3-可选»(Thomassen 1995—— «围长 5 ⟹ 3-可选»);③«平面 «三角剖分»» 的 «4-可选»(«四色定理的 «列表»» 在 «三角剖分» 情形已证——Thomassen 的 « «面» 归纳»);④一般平面图的 «4-可选» 开放。□
进展与文献
Thomassen(JCTB 1994 的 5-可选、1995 的围长系列);Voigt–Wirth 的反例;Dvořák–Postle 的 DP 框架(2015+);Bernshteyn–Kostochka–Pron 的 «DP-4 反例»。开放核心:一般 4-可选;«4-可选 ⟺ 无 «特定 «匹配»»» 的 DP 中间地带刻画;«列表四色定理» 若成立将 «统一» 列表染色理论。