algorithm - 无向图的着色

给定一个具有边数和颜色值的无向图。因此，我们必须检查图形是否可以用不同的颜色着色，条件是没有两个相邻的顶点颜色相同。emm

我有一个想法，对于每个顶点，如果顶点的度数 < m，那么我们可以用颜色为图形着色m。

如果对于任何顶点，度数 >= m，那么我们不能用颜色为图形着色m。

我使用上述方法并尝试解决 M-Colouring 图，但没有奏效。

有人可以告诉我，为什么上述方法不起作用？

m我对给定= 3、顶点数 = 4、边 =e 其中边为 4->3、4->2、1->4、3->2、1->2的测试用例之一存有疑问.

也就是说，我们可以用 3 种颜色为上面的无向图着色。怎么可能？顶点 4 的度数是 3，所以相邻顶点的个数是 3。如果我把顶点 4 本身包括在内，则有四个相邻顶点。我们如何只用 3 种颜色为这四个相邻的顶点着色？我认为这是不可能的。如果我以错误的方式思考，请告诉我。

如果问题或提出问题的方式有任何问题，请在下面发表评论，这会有所帮助。

标签： algorithmcolorsgraph-algorithmundirected-graphgraph-coloring

一个节点的两个邻居可以有相同的颜色，例如，图

1----2
|    |
|    |
4----3

是 2-colorable 的，因为我们可以用颜色 1 为奇数顶点着色，用颜色 2 着色偶数顶点。对于每个顶点 v，v 的邻居具有相同的颜色，这与 v 的颜色不同，因此不存在违规。