超圖的頂點着色，不均勻性限制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。