人工智能推翻了一个20世纪90年代的着色猜想

取一个由线连接起来的点构成的网络——即一个图。全着色为每个点和每条线都分配一种颜色，并遵守三条规则：相邻的两个点颜色不同，交于同一点的两条线颜色不同，一条线与它的两个端点颜色不同。能满足要求的最少颜色数称为全色数，记作χ″(G)。

现在增加难度。给每个点和每条线分配一个专属列表，列出允许使用的颜色，所有列表大小相同，都为k，并要求从列表中选出颜色构成一种合法着色。无论列表如何都能做到的最小k，称为列表全色数，记作χ″ℓ(G)。它永远不会小于χ″(G)：如果所有列表都相同，就回到了普通问题。

一个20世纪90年代末的猜想

三组研究者——Borodin、Kostochka和Woodall；Juvan、Mohar和Škrekovski；Hilton和Johnson——在20世纪90年代末各自独立地提出，专属列表永远不会带来额外代价：

对每个图（即使两点之间有多条线），χ″ℓ(G) = χ″(G)。

这就是列表全着色猜想（List Total Colouring Conjecture）。已有证据支持它：对于没有任何点连着超过两条线的图，该猜想成立；而且已知每个点恰好连着三条线的图（即三正则图）从列表中着色最多需要5种颜色。

反例

加拿大维多利亚大学的Jonathan Noel如今给出了一个有20个顶点的三正则图，其χ″ = 4，而χ″ℓ = 5。猜想不成立。

构造十分简洁。取四个名为K₂,₃的小图的副本：两个“私有”点，各自连接到相同的三个“终端”点。然后在每两个副本之间，用恰好一条连接终端的“交叉”线把它们连起来。这样每个点最终都连着三条线。

只用四种颜色完成全着色的图G，颜色以形状和线型表示。——图1，Noel（2026），arXiv:2609.38417。

在普通的着色游戏中，四种颜色就够了：颜色4分配给所有私有点和所有交叉线，它们彼此从不相接；其余部分由一张小表格和一条循环规则来处理。

无法满足的列表

这个陷阱使用1到5号颜色。区块i中的每个点和每条线得到的列表是“除i以外的所有颜色”；交叉线则得到精心挑选的列表，缺少5或i + 2。证明过程就像一个简短的侦探故事：

• 引理：在K₂,₃的任何4色着色中，两个私有点必须颜色相同。
• 因此，每个区块i都有一对颜色{i, sᵢ}，而两个区块之间的每条交叉线都必须使用这两对颜色共有的一种颜色。
• 稍加计数就可以证明，必有一种颜色t同时属于全部四对颜色。
• 对于t的每一种可能取值，都有某一条特定的交叉线，其列表中恰好缺少这种颜色。矛盾。

列表分配：每个点和每条线可以使用1到5中除标注颜色以外的任何颜色。没有任何全着色能满足这些列表。——图2，Noel（2026），arXiv:2609.38417。

由机器发现，由数学家核验

这篇论文对其来历的坦率程度非同寻常。2026年9月24日，Noel提示ChatGPT 6 Astra Ultra去推翻这一猜想，而它给出了反例，“作者几乎没有提供什么输入”。他核查了论证，并根据模型生成的草稿重新撰写了文本；模型还协助校对、推荐了参考文献并绘制了图表。声明的最后一句是：“作者对正确性承担全部责任。”这篇论文是预印本，但证明足够简短，任何有耐心的读者都可以自行验证。

相差一种，还是更多？

专属列表可能多用一种颜色。它们能多用更多吗？如果相差三种，那么一个被深入研究的“近亲”——列表边着色猜想（List Edge Colouring Conjecture）——也会随之倒下，因为χ″ℓ ≤ χ′ℓ + 2且χ″ ≥ χ′。Noel在文末提出了一个人工智能的反例仍未解决的开放问题：是否对每个图都有χ″ℓ(G) ≤ χ″(G) + 1？