总染色猜想（Δ=6）自动放电框架构建完成

2026年5月19日至21日，路宇轩、英启锐、卢志钧围绕最大度 (\Delta=6) 的平面图总染色问题展开集中攻关，完成了基于自动放电（Automatic Discharging）框架的构型生成与线性规划（LP）建模方案设计。

问题背景与方法论

总染色猜想（TCC）断言任何简单图 (G) 可在 (\Delta+2) 种颜色下完成全染色（同时为顶点和边着色，相邻/关联元素颜色不同）。(\Delta=6) 的平面图是 TCC 最后一个未解决的情形。

本次工作采用 Bousquet, Deschamps, de Meyer 与 Pierron 在 SIAM 2024 中提出的自动放电框架，核心流程为：先生成所有局部构型（面和顶点周围的循环字符串），再求解 LP 寻找使 (\alpha) 最大化的放电规则，目标达到 (\alpha \ge 4)。若未达到，则从 LP 对偶中提取紧约束，手工或算法证明其可约性后加入 (Red) 集合，迭代重解直至收敛。

与旧方案的关键差异

相比之前的方案，新框架做出了几项重要调整：

• 6-顶点完全参与 LP。旧方案将 6-顶点排除或隐式处理，新方案新增 vertex_6 构型类，使其与 3/4/5-顶点统一参与 LP 建模。
• 面类型语义重新定义。(H) 面由原来的"6⁺-面"收紧为精确的 6-面，(O) 面表示 7⁺-面，LP 自行决定放电权重，不预设任何硬编码约束。
• 废除 4-fan 条件。由于 (\Delta=6) 的总染色问题不涉及该结构条件，将其从框架中完全移除。
• 构型类从 6 类扩展至 8 类。新增 face_6 和 vertex_6，覆盖全部面与顶点的局部构型空间。

构型生成与结构过滤

构型以交替的 digit/face 字符串表示（如 4H5H6H 表示三角形，顶点度数为 ((4,5,6))，三入射面均为 6-面）。字符串长度等于 (2d)（(d) 为面或顶点的度）。

参考 Zhu & Xu (2017) 的结构引理，在生成阶段即引入过滤器排除极小反例中不可能出现的构型，大幅压缩搜索空间。核心过滤规则包括：

• Corollary 2.2：3-顶点仅能与 6-顶点相邻（(3+3=6\le 8)，(3+4=7\le 8)，(3+5=8\le 8)）
• Lemma 2.3：3-顶点不可位于三角形上
• Lemma 2.4：三角形至多含一个 4-顶点
• Lemma 2.5：三角形不可含 ((4,5,5)) 模式
• Lemma 2.6：6-顶点至多 4 个 3-邻居

算法设计上，采用了 Digit-Canonical 预过滤策略：先枚举 digit 组合并用 Corollary 2.2 过滤，再对 digit-canonical 模式展开 face 组合，最后做完整的偶步旋转 canonical 检查。对 (d=6)，digit 组合从 (4^6=4096) 压缩至 162 个 digit-canonical patterns。

生成结果

运行 gen.py --verify（Python 3.12，总耗时约 15 秒）得到如下结果：

总计约 314 万条 canonical 构型（face 157.7 万 + vertex 155.7 万），输出为 8 个文本文件，总计约 70 MB。

LP 求解策略：约束生成

面对约 314 万条构型约束 × 约 3,500 个变量的 LP，直接求解虽理论可行（GLPK 单纯形法，数小时级别），但效率偏低。

采用约束生成（Constraint Generation）策略：初始仅随机采样约 5,000 条约束求解，再扫描全部构型找出违规约束，将最违规的若干条加入工作集后重新求解。每一轮 LP 求解（~5,000×3,500 稀疏矩阵）仅需数秒，扫描全部约束约 0.5 秒，预期 3–8 轮收敛。总 LP 求解时间控制在 1 分钟以内。

下一步工作

1. 变量系统：实现 VV/FF/FV 三族变量的生成，从构型字符串自动推导
2. LP 框架重写：构建新的约束矩阵并实现约束生成循环
3. (Red) 集合管理：建立 (Red) 目录，将当前过滤器转化为可约构型模式文件
4. 完整迭代：运行 LP → 识别紧约束 → 规约 → 重复，直至 (\alpha \ge 4)