Réduction d'une coloration M à une partition M

Question

Définir une partition M comme: donné un graphique non dirigé g= (v, e) et un entier j.Existe-t-il une partition des sommets dans des parties M {v1, v2, ..., vm} de telle que au moins J des bords aient leurs points d'extrémité dans différentes parties de la partition?

J'ai commencé par partitionnement du graphique dans les parties K: chaque partition représente une coloration du graphique.À partir de là, j'ai pensé à revenir à tous les bords: convertir ainsi tous les bords en non-arêtes et inversement.Je suis coincé ici.Suis-je sur la bonne voie?Merci.

Answer 1

Par définition, une $ M $ -coloring est une fonction $ f: v \ to \ \ to \ \ \ points, m \} $ tel que $ \ Forall u, v \ in v \; f (u)= f (v) \ implique (u, v) \ pas \ in e $ . Cela signifie qu'au moins $ | e | $ Les bords ont leurs points d'extrémité dans différents ensembles de la partition $ \ {v_1, \ points, v_m \} $ de $ v $ avec $ v_i={v \ in v: f (v)= i \} $ .

au contraire, s'il y a une partition $ \ {v_1, \ dots, v_m \} $ de $ V $ tel que au moins $ | e | $ Les bords ont leurs points d'extrémité dans différents ensembles, puis la fonction $ f: v \ to \ to \ {1, \ points, k \} $ , où $ f (u) $ est l'index unique $ i_u \ in \ \ {1, \ dots, m \} $ tel que $ u \ in a_ {i_u} $ , satisfait $ \ Forall u, v \ in v \; f (u)= f (v) \ implique (u, v) \ pas \ in e $ .

Ce qui précède montre que l'instance $ g= (v, e) $ de $ m $ -Coloration peut être réduite (réductions KARP WRT) à l'instance $ \ LBOUS G, | E | \ rangs $ de $ M $ -Partition.