图的着色临界性 图的着色临界性理论关注的是那些在移除任意顶点（或边）后色数严格减小的图，这类图对理解图的着色结构与最优着色算法有重要意义。 第一步：定义与基本例子 一个图 \( G \) 称为 顶点着色临界 （通常简称“临界图”），如果对于它的每个真子图 \( H \subset G \)，其色数满足 \( \chi(H) < \chi(G) \)。最常见的临界图是奇环（如三角形、五边形等），其色数为3，但去掉任意一条边后色数降为2。另一个经典例子是 \( K_ 5 \)（完全5个顶点的图），色数为5，去掉任一顶点后变为 \( K_ 4 \)，色数为4。 第二步：临界图的必要条件 狄拉克（G. A. Dirac）在1950年代证明了一系列性质： 任何k-色临界图（即色数为k的临界图）的最小度至少为 \( k-1 \)。 临界图是连通的，并且不能通过删除少于 \( k-1 \) 条边而变为不连通。 如果移除一个顶点后色数减少，那么该顶点的度至少为 \( k-1 \)。这些性质揭示了临界图的“脆弱性”：它处于某种极值状态，任何局部破坏都可能降低着色需求。 第三步：边临界图 类似地，可以定义 边着色临界图 ：如果去掉任意一条边后边色数 \( \chi'(G) \) 减小。根据维津定理（Vizing's theorem），任何简单图的边色数为 \( \Delta \) 或 \( \Delta+1 \)。边临界图在研究边着色分类（第一类或第二类图）时尤为重要。例如，奇环是边临界图，边色数为3（\( \Delta=2 \)，但 \( \chi'=3 \)），去掉任一边后边色数变为2。 第四步：临界图的结构与构造 哈约什（Hajós）构造：从两个k-色临界图出发，通过“粘合”一条边并删除另一条边，可以生成新的k-色临界图。这一构造能产生所有色数至少为2的临界图。 临界图不一定是完全的，但往往包含许多团结构。例如，所有4-色临界平面图（即每个真子图可3-着色）构成了研究四色定理的核心对象。 在边着色中，第二类图（\( \chi' = \Delta+1 \)）的临界图具有高度结构化性质，例如它们必须包含某些特定子图（如“过度饱和”顶点）。 第五步：临界性的算法意义 在着色算法中，临界图代表了“最难着色”的实例：贪心着色算法在临界图上通常达到最坏性能。识别图的临界子结构有助于设计分支定界或归约规则，例如： 在精确着色算法中，若发现一个k-色临界子图，则可立即确定该部分至少需要k种颜色，从而剪枝。 某些近似算法会反复删除非临界顶点（或边），将图简化为一个临界核，再对其进行处理。 第六步：推广与变种 列表着色临界性 ：考虑每个顶点有专属颜色列表的列表着色。若图在列表着色意义下是临界的，则其性质比普通临界图更严格，与可选择性（choosability）密切相关。 分数着色临界性 ：将色数替换为分数色数，研究分数着色意义下的临界图，这类图与超图的边覆盖数有关。 唯一可着色临界图 ：指那些不仅色数为k，而且所有k-着色都本质相同的临界图，这类图的结构更加受限。 通过上述步骤，图的着色临界性从一个简单的极值定义出发，逐步深入到结构刻画、构造方法与算法应用，成为连接图着色理论与组合极值问题的重要桥梁。