Reducción de un color m para una partición M

Question

Defina una partición M como: dado un gráfico no dirigido g= (v, e) y un entero j.¿Existe una partición de los vértices en las piezas M {V1, V2, ..., VM} de modo que al menos j de los bordes tengan sus puntos finales en diferentes partes de la partición?

Comencé particionando el gráfico en las piezas K: Cada partición representa 1 coloración de la gráfica.A partir de ahí, pensé en revertir todos los bordes: así que convirtiendo todos los bordes en los no bordes y viceversa.Estoy atorado aqui.¿Estoy en el camino correcto?Gracias.

Answer 1

Por definición, un $ m $ -coloring es una función $ f: v \ a \ {1, \ DOTS, M \} $ tal que $ \ forall u, v \ in v \; f (u)= f (v) \ implica (u, v) \ no \ in e $ . Esto significa que al menos $ | e | $ los bordes tienen sus puntos finales en diferentes conjuntos de la partición $ \ {v_1, \ DOTS, V_M \} $ de $ v $ con $ v_i={v \ in v: f (v)= i \} $ .

Por el contrario, si hay una partición $ \ {v_1, \ dots, v_m \} $ de $ V $ de modo que al menos $ | e | $ los bordes tienen sus puntos finales en diferentes conjuntos, luego la función $ F: v \ to \ {1, \ dots, k \ \} $ , donde $ f (u) $ es el índice único $ i_u \ in \ {1, \ dots, m \ \ _ $ tal que $ u \ in a_ {i_u} $ , satisface $ \ forall u, v \ in v \; f (u)= f (v) \ implica (u, v) \ no \ in e $ .

Lo anterior muestra que la instancia $ g= (v, e) $ de $ m $ -Colorado se puede reducir (reducciones de WRT KARP) a la instancia $ \ langosto g, | e | e | \ Rangle $ de $ m $ -partition.