超图的顶点着色，不均匀性限制NP-hard？

Question

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

Answer 1

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

A k-coloring超图H =（V，E）是一个函数，用于从{1,2，...， 。 。 ，k}给H的顶点，使得没有边是单色的（没有边具有相同颜色的所有顶点 - 除了单例）。

超图H的色数是H承认k着色的最小整数k。

超图H =（V，E）被称为r均匀，如果所有的边都有基数（大小）r。超边（e）的基数是（e）中顶点的数量。

你已经发现r-均匀超图的r-染色是r- = 3。如果这是真的（这是真的），那么对于一般的超图是NP难的，因为这是比一般超图更小的问题。

为了让您确信这是真的，让我们来看看r均匀超图的Berg定义1。这等同于上述定义。

让我们表示R（H）=最大|电子_我 |，和s（H）=分钟|电子_我 |。如果r（H）= s（H），H是r-均匀超图。现在，如果我可以在polynomail时间内对此进行着色，这意味着我找到H承认k着色的最小整数k。那么对于s（H）可能小于r（H）的一般超图，我们将能够在多项式时间内对顶点着色。

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