是否可以对图形进行着色，使相邻的顶点颜色不同，而不相邻的顶点颜色相同？
Can a graph be colored such that adjacent vertices are different colors and non-adjacent vertices are the same color?
给定一个图，是否有一种有效的算法来为其顶点着色，使得任意两个相邻的顶点颜色不同，任意两个不相邻的顶点颜色相同，并且使用最少的颜色数？
我意识到的是，除了图没有边的微不足道的情况外，它必须是连通的，否则这样的着色是不可能的：取任何现有的边u-v，很明显任何其他顶点x必须连接到它的端点之一，否则 color(x) = u 和 color(x) = v，与 color(u) != color(v).
相矛盾
关于如何解决这个问题还有其他想法吗？
让我们考虑具有边集补集的图，即当顶点不在原始图中时它们是相邻的，反之亦然。
在此新图中，相邻的顶点必须具有相同的颜色。这意味着，构成连通分量的所有顶点必须具有相同的颜色。此外，如果着色是可能的，则此连通分量必须是完整图（即所有顶点成对相邻），否则分量中有两个节点在原始 gaph 中相连，因此必须具有不同的颜色：矛盾。
现在，新图中的每个连通分量都必须有不同的颜色。
给定一个图，是否有一种有效的算法来为其顶点着色，使得任意两个相邻的顶点颜色不同，任意两个不相邻的顶点颜色相同，并且使用最少的颜色数？
我意识到的是，除了图没有边的微不足道的情况外，它必须是连通的，否则这样的着色是不可能的：取任何现有的边u-v，很明显任何其他顶点x必须连接到它的端点之一，否则 color(x) = u 和 color(x) = v，与 color(u) != color(v).
相矛盾关于如何解决这个问题还有其他想法吗？
让我们考虑具有边集补集的图，即当顶点不在原始图中时它们是相邻的，反之亦然。
在此新图中，相邻的顶点必须具有相同的颜色。这意味着，构成连通分量的所有顶点必须具有相同的颜色。此外，如果着色是可能的，则此连通分量必须是完整图（即所有顶点成对相邻），否则分量中有两个节点在原始 gaph 中相连，因此必须具有不同的颜色：矛盾。
现在，新图中的每个连通分量都必须有不同的颜色。