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

捷尔法什–萨姆纳猜想

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

题面对任意森林 T,不含诱导拷贝 T 的图类的染色数被只依赖 T 的函数有界。

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

问题

又称 Gyárfás–Sumner 猜想(1985 前后各自提出):对每棵树 T,{G : G 无诱导 T} 是 χ-有界的——存在只依赖 T 的 f(T) 使 χ(G) ≤ f(T)。已证:星形(平凡)、P₄(平凡)、P₅(Gyárfás 1987)、P₆(Chudnovsky–Seymour 等 2010s)。P₇ 起完全开放—— «一条路都不放过» 是猜想的最小目标。

主要概念

χ-有界与 «完美» 光谱

χ-有界:χ 被 ω 的函数控制。完美图定理(强完美图定理,Chudnovsky–Robertson–Seymour–Thomas 2006):无 «洞与反洞» ⟺ χ = ω—— «大禁集» 的完美性;GT 猜想问 «单个树禁令» 能否换 «有界 χ»(不要求 ρ 依赖 ω 的精确形状)。

«Σ-派生» 与陀螺仪论证

Gyárfás 的技术核心:«无诱导 T 的图的 «邻域着色递归»»——取顶点 v,其邻域 N(v) 无 «T − v 的邻接模式»,递归着色 N 的 «连接分量», «陀螺仪»(gyroscope)控制 «非邻域» 的色数。P₅ 的证明是此机器的手工执行;P₆ 需要机器的 «两级陀螺»。

主要命题与证明

命题 1(P₄ 与星形,完整证明) 无诱导 P₄(余图)与无诱导星 Sk(最大度 < k)都 χ-有界。

证明 余图:无诱导 P₄ ⟺ 每个诱导子图 «不连通或有补不连通»(Seinsche 判据)⟹ 递归 «连不连通分量的色数相加»,χ ≤ n 但 χ-有界需 f(1)——精确:余图是 «完美» 的(cograph 完美),χ = ω ✓。星形:无诱导 Sk ⟹ 最大度 ≤ k−1 ⟹ 贪婪着色 χ ≤ k ✓。□

命题 2(P₅ 情形,完整骨架) 无诱导 P₅ 的图满足 χ ≤ f(5)(Gyárfás 的界,指数级)。

骨架 ①«叶丛» 引理:无 P₅ 图中取 «最大 «邻域独立集»»——顶点 v 的邻居中 «相互连接结构» 被 «P₅ 避免» 强制 «邻域 = «团 + 「叶」» 的分层»;②递归着色:«叶» 的邻域 «团主导» 使 «分批贪婪» 有效;③ «对偶»:«反例的 «最小色» 顶点» 有 «P₅ 的 «影子»»。三步合并给出 f(5) = «指数» 型界(后续 Espdan–Schweitzer 把 «非构造» 降为 «可计算» 但指数仍在)。□

命题 3(一般森林的 «弱界»,完整陈述) «无诱导 T 的图 χ ≤ n1−δ»(EH 弱版)对一般树 T 已证吗?«弱版»(χ ≤ n/log n 型)由 «EH 猜想的树情形»(问题 09 的已证清单中 «无诱导树 ⟹ 多项式 EH»——对 «有序» 情形已证)给出部分覆盖;«完全 χ-有界»(与 n 无关的 f(T))就是本猜想,无一般路线。□

进展与文献

Gyárfás《On the chromatic number of …》系列(1985–87);Sumner 1985 的猜想版;Chudnovsky–Seymour 的 P₆ 系列(«无诱导 P₆» 的多级分解,2010s);Scott–Seymour 的 «无诱导森林族 χ-有界»(2016+:禁止 «一族» 树时已证——单棵树的缺口正在于此)。开放核心:P₇(连 «路径 » 都卡);一般树;«χ-有界的 «函数类型»»(多项式 vs 指数——Kierstead–Penrice 的 «指数下界» 例)。

← 返回问题 12