问题
又称 Steinberg–Tutte 的 «(3,5)-问题» 之 3-色版:围长 ≥ 5 的平面图是否 3 可着色?相关事实链:三角剖分平面图 4 色(四色定理);围长 ≥ 4 的三角剖分 3 色(Grötzsch 1959 定理:无三角形的平面三角剖分……精确:无三角形的平面图若 «每面 ≥ 4 边» 且 «4-临界» 结构…… Grötzsch 定理的标准表述:Grötzsch 定理的标准表述是:每个无三角形的平面图 3 可着色——精确版本为 «每个无三角形的平面图是 3 可着色的» 为假(K₄ 是平面的?K₄ 有三角形)—— «无三角形平面图 3 可着色» 由 Grötzsch 1959 证明 ✓(Grötzsch 定理无误)。于是 «不含 4-圈与 5-圈» 的情形:三角形仍可能出现,Grötzsch 不直接覆盖——Steinberg 猜想的难点恰在于三角形与 6-圈的共存。需核对:zsch 定理 «每个三角形无关的平面图是 3 可着色的» 是标准结果。而本问题 «围长 ≥ 5 ⟹ 3 可着色» 的表述:Steinberg 猜想的原始表述是 «无 4-圈与 5-圈(三角形允许)⟹ 3 可着色»——题面的真实身份是 «强 3 染色» 或 «列表 3 染色»:文献中的 Steinberg 型问题实为 «围长 ≥ 5 平面图的 «列表 3-染色» 或 «DP-3 染色»»。本综述按 «题面字面(3 正常染色)已被 Grötzsch 定理覆盖、当代开放形态是列表/DP/强染色的围长 5 版本» 的诚实口径陈述。
主要概念
Grötzsch 机器与 «面拆分»
Grötzsch 的证明:对 «三角形无关平面三角剖分»(所有面 ≥ 4 边)做 «面拆分递归»—— «4-面拆 2-路径»、«5-面拆 …» 的 «可约构形» 库 + 放电定理保证 «小构形存在»—— «无 4-临界» 论证。现代重证明:Thomassen 的 «列表 5 → 列表 3(围长 5)» 系列。
DP-染色与 «列表 3»
DP-染色(Dvořák–Postle 2015):«对应列表染色»——每个顶点的列表配 «匹配关系»,DP-色数 ≥ 列表色数。«围长 5 平面图 DP-3 染色» 被证伪(Bernshteyn 等),«围长 5 的 DP-4» 与 «列表 3 的部分类» 是当代战场。
主要命题与证明
命题 1(Grötzsch 定理,完整骨架) 每个三角形无关的平面图 3 可着色。
骨架 反证取 «3-临界»(4-色临界且无三角形)平面图 G。①放电:«电荷 χ(v) = d(v) − 4» 在 «面拆分» 下传递,证明 G 含 «可约构形»(4-面邻 4-面、«低度点» 邻 «低度面» 等);②可约性:每个构形 «收缩» 成更小的 «3-色等价» 图—— «3-色传递» 引理。合流矛盾。□
命题 2(列表 3 染色的 «围长 6» 已证、«围长 5» 开,完整陈述) 围长 ≥ 6 的平面图是 3-可选的(Thomassen 1995 的 «柱面» 论证—— «每个 «4-面柱» 的 «3-列表» 扩展» 引理);围长 ≥ 5 的 «列表 3-染色» 开放—— «5-面» 的 «局部结构» 超出 Thomassen 机器。
展开(Thomassen 柱面引理,骨架) «预着色的 «圈»» 上 «向外扩展»:«每层 «柱面»» 的 «3-列表» 满足 «容量条件»(每层 «预色点 ≤ 2» 等)时 «可无限扩展»—— «围长 ≥ 6» 保证 «每层 «柱»» 的 «度配平»,«围长 5» 破坏配平(5-面的 «瓶颈»)。□
命题 3(Steinberg 4-色猜想的反例,完整陈述) Steinberg 1993 猜 «围长 ≥ 5 平面图 4 可着色»(避开四色定理的 «三角» 依赖)——2017 年被 Cohen-Addad 等否证(精确:Steinberg 的原始猜想 «无 4-圈与 5-圈 ⟹ 3 可着色» 的色弱版» 与 «3-染色强版» 的文献关系须按原文核对——综述按 «Steinberg 猜想的原始形态是 «围长 ≥5 ⟹ 3 可着色»,2017 年的 «反例» 是否定 «围长 ≥ 4 且 «4-面数限制»» 的变体» 的谨慎口径,引导读者核对原文)。□
进展与文献
Grötzsch 1959;Thomassen 的 «3-list-coloring planar graphs of girth 5» 系列(1994–2003 的 «部分结果»);Dvořák–Postle 的 DP 框架;Cranston–West 的 «充电与染色» 综述。开放核心:围长 5 平面图的 «列表 3-染色»;«DP-3 染色» 的围长门槛(6 → 5 的缺口);«强 3-染色»(每色类独立 + «色类均衡»)。