Variation de coloration graphique

Question

Y a-t-il des variations du problème de coloration graphique classique que le nombre de voisins de la même couleur est limité mais pas zéro (dans le problème initial, la limite est zéro)?

Problème: donné un graphique $ g $ et deux entiers $ C $ et $ p $ est-il possible de colorer les sommets de $ g $ avec $ C $ couleurs telle que pour chaque sommet $ v $ avec couleur $ \ text {color} (V) $ ,

$$ |\ {w \ in n_g (v) \ mid \ texte {couleur} (v)=texte {couleur} (w) \} |\ Leq p? $$

Answer 1

La définition que vous recherchez est "Coloriage défectueux" :

a $ (k, d) $ -Coloring d'un graphique g est une coloration de ses sommets avec des couleurs K de telle sorte que chaque Vertex V ait à la plupart des voisins DAvoir la même couleur que le sommet v. Nous considérons que k comme un entier positif (il est sans conséquence de considérer le cas lorsque k= 0) et D être un entier non négatif.Par conséquent, $ (k, 0) $ -Coloring équivaut à une coloration de sommet adéquate.

Le nombre minimum de couleurs K requis pour lequel g est $ (k, d) $ -colourable est appelé la $ D $ Numéro chromatique -Défectif, $ \ chi _ {d} (g) $ .

.

Answer 2

Je ne connais pas cette variante, mais elle est toujours NP-complète pour tout $ P $ .

donné un graphique $ g $ et un entier $ C $ , connectez-vous à chaque sommet $ v $ une clique $ c_v $ sur $ (p + 1 ) C-1 $ sommets.

Si le graphique d'origine $ g $ a une coloration valide $ \ chi $ , alors nous pouvons Couleur de la clique $ C_V $ comme suit: la couleur $ \ chi (v) $ apparaît $ p $ fois et toutes les autres couleurs apparaissent $ p + 1 $ fois. Vous pouvez vérifier que chaque sommet a exactement $ p $ voisins de la même couleur.

Inversement, supposons que le nouveau graphique ait une coloration $ \ chi $ dans laquelle chaque sommet a au plus $ p $ voisins de la même couleur. Ceci n'est possible que si chaque couleur dans $ c_v $ apparaît au plus $ p + 1 $ fois, et Donc, une couleur $ \ chi '(v) $ apparaît $ p $ fois et le reste apparaît < SPAN CLASSE="MATH-CONTENEUR"> $ P + 1 $ fois. Cela implique que $ \ chi '(v)=chi (v) $ (car sinon la classe="math-conteneur"> $ v $ aurait $ P + 1 $ voisins avec les mêmes couleurs), et en outre que $ \ chi $ restreint aux sommets d'origine est une coloration valide (dans le sens habituel).