顶点着色，上限在节点的程度上

cs.stackexchange https://cs.stackexchange.com/questions/2690

题

考虑到顶点的最大程度是常数$ delta $独立于顶点数的恒定数字$ delta $的图集。顶点着色问题（即，为顶点涂上最小数量的颜色，以至于相邻节点没有相同的颜色）在此集合中仍然是NP-HARD？为什么？

有帮助吗？

解决方案

是的，它仍然是NP-HARD。对于平面度4图[1]，3-COL仍然是NP完整的。

  1. DALEY，DP（1980）， “平面4-规范图的可着色性和可着色性的独特性是NP完整的”, ，离散数学30（3）：289–293，doi：10.1016/0012-365X（80）90236-8
许可以下： CC-BY-SA 和 归因
不隶属于 cs.stackexchange
scroll top