图的收缩临界图与Hadwiger猜想 1. 基本动机：从图收缩到染色 图收缩是一种简化图结构的重要运算：将一条边e=(u,v)收缩，意味着将顶点u和v合并为一个新顶点，并与原来u和v的所有邻居相连。这个操作可能会产生重边，但通常会删除自环。一个核心观察是：如果图G可以通过一系列边收缩操作变成另一个图H，那么H的色数（对顶点着色所需的最少颜色数）一定不超过G的色数。因为如果G能用k种颜色着色，那么收缩操作后，被合并的顶点颜色相同，着色方案可以自然诱导到H上。 2. 收缩临界图的定义 对于一个整数k ≥ 1，如果一个图G满足以下三个条件，则称其为k-收缩临界图： G的色数 χ(G) = k。 对于G中的任意一条边e，收缩e后得到的新图G/e的色数 χ(G/e) < k。也就是说，收缩任何一条边都会导致图的色数下降。 G是边极小的k-色图，即删除G中任何一条边，图的色数都会降至k-1。 简单来说，k-收缩临界图是“结构最紧凑”的k-色图。它本身需要k种颜色着色，但任何微小的简化（删除或收缩一条边）都会降低其着色难度。著名的Hajós构造可以生成所有k-色图，而k-收缩临界图是这类构造中的核心构建块。 3. 小k值的临界图结构 当k=1时，只有空图（没有边）。 当k=2时，临界图是边极小的2-色图，即树（任何一棵树都是2-色图，但删除任何一条边会使其不连通，色数仍为2？这里需要修正：对于k=2，临界图实际上是任意一条边。因为2-色图是二分图，边极小的二分图就是任意一条边本身，因为删除该边后图变为不连通，每个连通分量是单个顶点，色数为1）。 当k=3时，临界图是奇圈（例如三角形、五边形等）。奇圈需要3种颜色，但删除或收缩任何一条边都会得到一个偶圈或路径，它们都是2-色图。 当k=4时，情况变得复杂。临界图不一定是完全图K₄。例如，Grötzsch图（一个没有三角形的图）的某种加强变体可以是4-临界图。但完全图K₄本身确实是4-收缩临界图。 4. Hadwiger猜想的引入 这是图论中最著名且未解决的猜想之一，由Hugo Hadwiger于1943年提出。猜想表述为： 如果一个图G的色数 χ(G) ≥ k，那么G必然包含一个完全图K₋作为其子式。 这里“子式”是关键。图H是图G的子式，如果H可以通过对G进行一系列边收缩、边删除和顶点删除操作得到。Hadwiger猜想断言，高色数的图在结构上必然复杂到包含一个大的“团”作为其核心骨架（通过收缩得到）。 5. 猜想与收缩临界图的深刻联系 Hadwiger猜想可以等价地重新表述为： 每个k-收缩临界图的顶点数必须大于或等于k，并且其结构必须允许其能收缩成完全图K₋。 这个等价形式揭示了研究收缩临界图的重要性。因为如果你能证明每个k-收缩临界图都包含K₋作为子式，那么对于任意色数为k的图G，你可以先通过删除边和顶点得到一个k-收缩临界子图，而这个子图包含K₋子式，那么原图G自然也包含K₋子式。 6. 猜想的已知结果与现状 当k ≤ 4时，猜想已被证明是正确的。例如，4-收缩临界图都被证明包含K₄作为子式（这相对容易证明）。 当k=5时，情况变得极其困难。猜想等价于著名的“四色定理”！因为四色定理说任何平面图都是4-可着色的，其逆否命题是：如果一个图是5-色的，它不可能是平面图。而Wagner定理表明，一个图是平面图当且仅当它不包含K₅或K_ {3,3}作为子式。因此，一个5-色图必然包含K₅作为子式。所以k=5的情形实际上与四色定理等价，并在1976年被Appel和Haken用计算机辅助证明。 当k=6时，猜想尚未被普遍证明，但已知的结果是：6-收缩临界图如果包含一个K₆子式，则猜想成立。目前的研究集中在分析6-临界图的结构，并证明其顶点连通度很高，从而可能通过复杂的组合分析找到K₆子式。 对于k≥7，猜想完全开放，是图论领域的顶级难题。 总结 图的收缩临界图是理解图着色复杂性的关键对象，它们代表了着色问题中“最难”的那类图。Hadwiger猜想将图的色数这一全局属性与其子式结构（特别是包含大团的能力）深刻地联系起来。该猜想在k≤6时已获证，但对于更大的k，它仍然是组合数学领域一个诱人而艰巨的挑战，推动着对图的结构，特别是收缩临界图性质的深入研究。