graph-theory - 当一个给定的图是 3 色的？

Question

我想使用图 3 可着色性来证明问题是 NP 完全的但是我不确定给定的图何时是 3 可着色的。我想如果它没有任何节点连接到图中三角形的所有 3 个顶点。但我不确定。正确吗？

Answer 1

没有。将一个节点连接到三角形中的所有三个节点(这只是说“它有一个大小为 4 的团”的更复杂的方式)就足够了但不是必要的，因为图不是 3 - 可着色。由于与具有大小为 4 的团不同的原因，图可能不是 3 色可着色的。

例如:

它不是三色的。证明:外面的5-cycle不是2-colorable的，然后中间的顶点需要额外的颜色。