グラフぬりえバリエーション

Question

同じ色の隣接者数が制限されていないがゼロではない古典的なグラフ色の問題の変動はありますか？

問題：グラフ $ g $ と2つの整数 $ c $ と $ p $ は、 $ g $ の頂点をに色付けることが可能です。$ c $ 色 $ v $ の色 $ \ text {color}（v））$ 、

$$ |\ {w \ in n_g（v）\ mid \ text {color}（v）=text {color}（w）\} |\ LEQ P？$$

Answer 1

あなたが探している定義は「不良着色」：

$（k、d）$ グラフGの色調は、各頂点vが最も隣接するようにv個の色との頂点の着色です。頂点vと同じ色を持つ。Kを正の整数にすることを検討します（k= 0の場合は、k= 0の場合は考慮することは重要ではありません）、dは負の整数であると考えています。したがって、 $（k、0）$ -coloringは、適切な頂点の着色と同等です。

gが $（k、d）$ の最小色数kは、 - 無効色番号、 $ \ chi_ {d}（g）$ 。

Answer 2

私はこのバリアントに精通していませんが、任意の固定 $ p $ のためのnp-completeです。

グラフ $ g $ とinteger $ c $ は、各頂点 $ v $ clique $ c_v $ $（p + 1 c-1 $ 頂点

元のグラフ $ g $ には、有効な色 $ \ chi $ があります。 Color Clique $ C_V $ 以下のように：color $ \ chi（v）$ が表示されます $ p $ 時間、および他のすべての色が $ p + 1 $ 回転します。すべての頂点に、同じ色の $ p $ の隣接があることを確認できます。

逆に、各頂点が $ pを持っている色付け $ \ chi $ を持っているとします。同じ色の$ 隣接。これは、 $ c_v $ の各色が $ p + 1 $ 時刻で表示される場合にのみ可能です。そのため、いくつかの色 $ \ chi '（v）$ が表示されます $ p $ 時間、そして残りは表示されます。 SPAN CLASS="math-container"> $ P + 1 $ 回数。これは、 $ \ chi '（v）=chi（v）$ を意味します（ $ v $ 同じ色の $ p + 1 $ neighbors、さらに $ \ chi $ 元の頂点に制限されている（通常の意味で）有効な着色です。