图的控制着色 基本控制概念铺垫 在图论中，控制集是图 \( G = (V, E) \) 的一个顶点子集 \( D \)，使得图中任意不在 \( D \) 中的顶点，都至少有一个邻居在 \( D \) 中。控制着色是控制概念的推广：我们需要为每个顶点分配一种颜色（用正整数表示），要求对于任意一种颜色，所有染成该颜色的顶点集合必须是一个控制集。也就是说，每种颜色类都需要独立地“控制”整个图——每个未被染成该颜色的顶点，必须至少有一个邻居是该颜色。 定义与实例 更形式化地，图 \( G \) 的一个 控制着色 是一个正常着色（相邻顶点颜色不同），同时它也是一种划分着色，其中每个颜色类都是 \( G \) 的一个控制集。 控制色数 记作 \( \chi_ d(G) \)，定义为使得 \( G \) 存在控制着色的最少颜色数。例如，一个完全图 \( K_ n \) 的控制色数是 \( n \)，因为每个顶点必须独自成为一种颜色（若两个顶点同色，则它们相邻，违反正常着色；若一种颜色只包含一个顶点，则该颜色类必须控制所有其他顶点，在完全图中这要求该顶点与其他所有顶点相邻，成立，但不同颜色间仍需正常着色条件，所以需要 \( n \) 种颜色）。 与经典着色的关键差异 经典着色数 \( \chi(G) \) 只要求相邻顶点不同色；而控制着色额外要求每种颜色类都是控制集。这意味着 \( \chi_ d(G) \geq \chi(G) \)，且通常严格大于。例如，一个不含孤立点的图，若用两种颜色正常着色（如二分图），但其中一个颜色类可能不是控制集（比如某侧顶点可能有一度顶点，若另一侧没有邻居染同色，则该颜色类不控制这些一度顶点），所以可能需要增加颜色数来满足控制条件。 简单图的控制色数下界与上界 对于任意阶数为 \( n \) 且没有孤立点的图，有 \( \chi_ d(G) \geq 2 \)（因为若只有一种颜色，则该颜色类需控制所有顶点，意味着所有顶点必须染同色，但正常着色要求相邻顶点不同色，除非图无边，矛盾）。一个平凡上界是 \( \chi_ d(G) \leq n \)，即每个顶点一种颜色。更紧的上界与图的支配数 \( \gamma(G) \) 有关：由于每种颜色类都是控制集，其大小至少为 \( \gamma(G) \)，因此颜色类个数不超过 \( \lfloor n/\gamma(G) \rfloor \)，但此上界可能被正常着色条件限制，实际研究中需更精细分析。 控制着色的构造与算法复杂度 已知判定 \( \chi_ d(G) \leq k \) 对一般图是 NP-完全的，即使对二部图或弦图也是如此。构造控制着色的一种贪心思路是：先找到一个极小控制集作为第一种颜色类，移除这些顶点后，在剩余图中再找控制集作为第二种颜色类，但要注意剩余子图的控制集可能不控制已移除的顶点（因为控制要求是针对原图的），因此需要修正或回溯。实际算法常基于分支或整数规划。 特殊图类的控制色数 完全图 \( K_ n \)：\( \chi_ d(K_ n) = n \)。 完全二部图 \( K_ {m,n} \)：当 \( m, n \geq 2 \) 时，\( \chi_ d(K_ {m,n}) = \min\{m,n\} + 1 \)（需要分析两侧顶点分配颜色的控制条件）。 圈图 \( C_ n \)：对于 \( n \geq 3 \)，有 \( \chi_ d(C_ n) = \lceil n/3 \rceil + 1 \) 或类似公式，具体依赖 \( n \mod 3 \) 的值（需要保证每种颜色类在原图中是控制集，并满足正常着色）。 树：控制色数可通过动态规划计算，与叶子和内部顶点结构相关。 与其它着色变体的关系 控制着色可视为正常着色与划分着色的结合，它不同于 支配着色 （每个顶点必须与某种颜色的顶点相邻，且着色正常），也不同于 广播着色 （要求颜色数表示距离覆盖）。控制着色强调每种颜色类全局控制，在资源分配、频道分配需备份覆盖的场景中有潜在应用。