图的符号图着色与符号色数 我们先从基础定义开始。符号图（signed graph）是图论中一个扩展概念。一个符号图 G = (V, E, σ) 由顶点集 V、边集 E 和一个符号函数 σ: E → {+1, -1} 组成。每条边被赋予一个“+”或“-”的符号，分别称为正边和负边。这可以用来表示二元关系中的友好/敌对、合作/冲突等状态。 在符号图中，着色问题变得更为复杂，因为我们需要考虑符号的影响。最经典的一种着色是“符号着色”（signed coloring），其目标是为每个顶点分配颜色，使得任意由一条边连接的两个顶点所获得的颜色满足一定的约束，这个约束取决于边的符号。 具体来说，对于一个符号图 G，一个“符号着色”使用一组颜色，这组颜色通常是从整数集合中选取，并且包含零、正数和负数。一种常见且系统的定义是使用“有符号整数”作为颜色集，例如颜色集为 { -k, …, -1, 0, 1, …, k }。着色的规则是：对于任意一条边 e = uv， 如果 e 是正边（σ(e)=+），则要求 c(u) ≠ c(v)。这和普通图着色的要求一样。 如果 e 是负边（σ(e)=-），则要求 c(u) ≠ -c(v)。这意味着两个顶点的颜色不能互为相反数。 理解这个规则的关键在于认识到，在符号图中，颜色本身是带符号的整数。规则确保了在正边上，颜色不能相同；在负边上，颜色不能是“敌对”（相反）的关系。这种设计巧妙地捕捉了符号所代表的关系：正边连接的顶点应“不同”（避免冲突），负边连接的顶点应“不相反”（避免直接对立）。 接下来，我们引入“符号色数”的概念。对于给定的符号图 G，其“符号色数”（signed chromatic number）χ±(G) 定义为：使得 G 存在一个使用颜色集 { -k, …, -1, 0, 1, …, k } 的符号着色的最小整数 k。注意，这里使用的颜色总数是 2k+1。这个定义是由 R. P. Stanley 和 T. Zaslavsky 等人系统研究后推广的。 为什么符号着色是有意义的？因为它与符号图的结构和平衡性密切相关。一个符号图是“平衡的”（balanced），如果它的每个圈包含偶数条负边。平衡的符号图在结构上等价于普通图（可以通过顶点重新赋值符号使其所有边为正）。对于平衡的符号图，其符号色数 χ±(G) 恰好等于其基础无符号图的普通色数 χ(G)。对于非平衡的符号图，符号色数通常会小于或等于普通色数，并且有独特的性质。 为了更深入地计算和理解符号色数，我们引入“双极开关”（switching）的概念。在符号图中，对顶点 v 进行“开关操作”是指改变所有与 v 关联的边的符号。经过一系列开关操作后得到的符号图与原图是“等价的”，它们的符号着色性质和平衡性是相同的。因此，在考虑着色问题时，我们可以在一个等价类中选取一个方便的符号图来进行分析。 符号色数有一个重要的“对偶”解释，它与“圆着色”有紧密联系。符号图 G 的符号色数 χ±(G) 与“有符号圆色数”（signed circular chromatic number）有关。具体来说，符号着色可以等价地看作是将顶点映射到单位圆上的点（考虑方向和距离），使得正边连接的点不重合，负边连接的点不处于对径点位置。这使得符号色数可以通过计算几何或优化问题来研究。 最后，我们看一个计算符号色数的简单例子。考虑一个由两个顶点和一条负边构成的符号图（一个负边2-顶点图）。如果我们使用颜色集 { -1, 0, 1 } （即 k=1），我们可以为两个顶点分别着颜色 1 和 0，因为 1 ≠ -0（0的相反数是0，1≠0）。所以这个图的符号色数 χ± = 1。而对于同样的两个顶点，如果它们之间是一条正边，那么普通色数为2，但作为符号图，我们至少需要 k=1 的颜色集 { -1,0,1 }，可以分别着颜色1和-1（满足1≠-1，且对于正边，1≠-1也成立），所以 χ± 也是1。这个例子显示，由于颜色集包含正、负和零，有时能用更少的“色数k”来实现着色。