Variación del gráfico para colorear

Question

¿Hay variaciones del problema de coloración clásico de gráficos que el número de vecinos en el mismo color es limitado pero no cero (en el problema original, el límite es cero)?

Problema: Dado un gráfico $ g $ y dos enteros $ C $ y $ P $ , es posible colorear los vértices de $ g $ con $ C $ colores de tal manera que para cada vértice $ v $ con color $ \ texto {color} (v) $ ,

$$ |\ {w \ in n_g (v) \ medio \ texto {color} (v)=texto {color} (w) \} |\ leq p? $$

Answer 1

La definición que está buscando es "Coloración defectuosa" :

a $ (k, d) $ -coloring de un gráfico G es una coloración de sus vértices con los colores de K de manera que cada vértice V tiene en la mayoría de los vecinos.Tener el mismo color que el vértice v. Consideramos que K para ser un entero positivo (es intrascendente considerar el caso cuando K= 0) y D para ser un entero no negativo.Por lo tanto, $ (k, 0) $ -coloring es equivalente a la coloración de vértices adecuados.

El número mínimo de colores requeridos para los cuales G es $ (k, d) $ -colorable se llama el $ d $ -defective Number Chromatic, $ \ chi _ {d} (g) $ .

Answer 2

No estoy familiarizado con esta variante, pero aún así es NP-completa para cualquier $ P $ .

Dado un gráfico $ g $ y un entero $ C $ , conecte a cada vértice $ v $ una camarilla $ c_v $ en $ (p + 1 ) C-1 $ vértices.

Si el gráfico original $ g $ tiene una coloración válida $ \ chi $ , entonces podemos Colorea la clique $ c_v $ de la siguiente manera: el color $ \ chi (v) $ aparece $ P $ veces, y todos los demás colores aparecen $ P + 1 $ tiempos. Puede verificar que cada vértice tenga exactamente $ P $ vecinos del mismo color.

A la inversa, suponga que el nuevo gráfico tiene un colorante $ \ chi $ en el que cada vértice tiene en la mayoría de $ p $ vecinos del mismo color. Esto solo es posible si cada color en $ c_v $ aparece en la mayoría de $ P + 1 $ veces, y así que un poco de color $ \ chi '(v) $ aparece $ P $ veces, y el resto aparecen < Span Class="Math-contenedor"> $ P + 1 $ tiempos. Esto implica que $ \ chi '(v)=chi (v) $ (desde que, de lo contrario, $ v $ Tendría $ P + 1 $ vecinos con los mismos colores), y además, que $ \ chi $ restringido a los vértices originales es una coloración válida (en el sentido habitual).