np-complete - 没有均匀性限制的超图的顶点着色是 NP 难的吗？

Question

没有均匀性限制的超图的顶点着色是 NP 难的吗？我看过一些论文，显示 k-unoform 超图的顶点着色是 NP 难的。但是，我找不到任何明确说明在一般情况下（不仅仅是 k-uniform）超图的顶点着色是否是 NP-hard 的来源。

Answer 1

在回答这个问题之前，有很多事情需要解释，例如超图中的着色和均匀性。我将在这里使用不同的符号。

超图 H = (V, E)的k 着色是一个从 {1, 2, . . . , k} 到 H 的顶点，使得没有边缘是单色的（没有边缘具有相同颜色的所有顶点 - 除了单例）。

超图 H 的色数是 H 允许 k 着色的最小整数 k。

超图 H=(V,E) 称为 r-uniform，如果所有边的基数（大小）恰好为 r。超边 (e) 的基数是 (e) 中的顶点数。

您已经发现 r>=3 的 r 均匀超图的 k 着色是 NP 难的。如果这是真的（这是真的），那么对于一般超图来说它是 NP-hard，因为这是比一般超图更小的问题。

为了让你相信这是真的，让我们看一下 r-uniform hypergraph 1的 Berg 定义。这等价于上面的定义。

让我们表示 r(H)=Max|E _i |，并且 s(H)=min|E _i |。如果 r(H)=s(H)，则 H 是 r-均匀超图。现在，如果我可以在 polynomail 时间内对其进行着色，这意味着我找到了 H 允许对其进行 k 着色的最小整数 k。然后对于一般超图，当 s(H) 可能小于 r(H) 时，我们将能够在多项式时间内为顶点着色。

要找到超图的色数的确切值是 NP 难的。