无向图的着色

Question

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

I have a thought that, for each vertex, if the degree of the vertex < m, then we can colour the graph with m colours.

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

我用上面的方法尝试解决M-Coloring graph，但没有成功。

谁能告诉我，为什么上面的方法不起作用？

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

也就是说，我们可以用3种颜色来给上面的无向图着色。怎么可能？顶点4的度数是3，所以，相邻顶点的个数是3。如果我加上顶点4本身，就有4个相邻顶点。我们如何只用 3 种颜色给这四个相邻的顶点着色？我认为这是不可能的。如果我的想法有误，请告诉我。

如果问题或提问方式有任何问题，请在下方评论，这将有所帮助。

Answer 1

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

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

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

Answer 2

从的 post 我了解到顶点的度数与图形着色没有任何关系。因为，在着色中，我们必须以一种方式着色，使得没有两个相邻的顶点具有相同的颜色。

根据我在问题中 posted 的例子，给定 m = 3。顶点的度数 4 是 3，在我的方法中我认为，因为顶点的度数为 4是 3，如果我包括顶点 4 本身，那么我们必须为这四个彼此相邻的顶点着色，我认为不可能只用 m 为四个顶点着色，即 3 种颜色。但事实并非如此。

即使顶点的度数 4 >= m（给定 m = 3）我们仍然可以用 3 种颜色给图着色。

这里的事情不是检查顶点的度数，而是对顶点应用颜色并检查其相邻顶点是否具有相同的颜色

Coloring of undirected graph