均一性の制限がないハイパーグラフの頂点の色付けはNP-hardですか？

Question

均一性の制約がないハイパーグラフの頂点の色付けはNP困難ですか？私は、k-unoformハイパーグラフの頂点の色付けがNP困難であることを示す論文を見てきました。しかし、私は、一般的なケース（k-ユニフォームではない）ハイパーグラフの頂点カラーリングがNPハードであるかどうかを明示的に示しているソースは見つかりませんでした。

Answer 1

この質問に答える前に、ハイパーグラフの色や均一性など多くのことを説明する必要があります。ここでは異なる表記を使用します。ハイパーグラフH =（V、E）は{1,2、...、N}からの色を割り当てる関数である。 。 。 、k}を、エッジが単色でない（エッジがシングルトンの他に同じ色のすべての頂点を持たない）ようにHの頂点に割り当てる。

ハイパーグラフHの有彩色数は、Hがk-着色を許容する最小の整数kである。

ハイパーグラフH =（V、E）はr-uniformと呼ばれ、すべての辺が正確にrの基数（サイズ）を持つ場合。ハイパーエッジ（e）の基数は（e）の頂点の数です。

r-ユニフォームハイパーグラフのr- = 3のk-カラーリングがNP-hardであることが既に判明しています。これが本当であれば（それは本当である）、これは一般的なハイパーグラフよりも小さい問題であるため、一般的なハイパーグラフについてはNP困難である。

これが本当であることを確信させるために、r-uniform hypergraph 1のBerg定義を見てみましょう。これは上記の定義と同じです。

のは、R（H）=マックスを表すもの|私は E _{|、およびS（H）=分| E 私は |。 r（H）= s（H）ならば、Hはr-uniformハイパーグラフである。今私は多項式時間で色を付けることができます。これは、Hがk-coloringを認めている最小の整数kを見つけたことを意味します。次に、s（H）がr（H）よりも小さくなる可能性のある一般的なハイパーグラフの場合、多項式時間に頂点を色付けすることができます。}

ハイパーグラフの色数の正確な値は、NP-hardです。