Variazione della colorazione del grafico

Question

Ci sono variazioni del classico problema di colorazione del grafico che il numero di vicini nello stesso colore è limitato ma non zero (nel problema originale il limite è zero)?

Problema: dato un grafico $ G $ e due numeri interi $ c $ e $ P $ , è possibile colorare i vertici di $ G $ con $ c $ colori in modo tale da ogni vertice $ V $ con colore $ \ Text {Color} (V) $ ,

$$ |\ {w \ in n_g (v) \ metà \ testo {color} (V)=testo {color} (w) \} |\ Leq P? $$

Answer 1

La definizione che stai cercando è "Colorazione difettosa" :

.

A $ (K, D) $ -Coloring di un grafico G è una colorazione dei suoi vertici con colori K in modo tale che ogni vertice v ha al massimo il vicinatoAvere lo stesso colore del vertice v. Consideriamo K per essere un intero positivo (è irrilevante considerare il caso quando k= 0) e D per essere un intero non negativo.Quindi, $ (k, 0) $ -Coloring è equivalente alla colorazione del vertice corretto.

Il numero minimo di colori K richiesto per il quale G è $ (K, D) $ -Colourable è chiamato $ D $ -Defective numero cromatico, $ \ chi _ {d} (g) $ .

Answer 2

Non ho familiarità con questa variante, ma è ancora NP-completa per qualsiasi classe fissa $ P $ .

Dato un grafico $ G $ e un intero $ c $ , connettersi a ciascun vertice $ V $ a clique $ c_v $ su $ (P + 1 ) C-1 $ Vertici.

Se il grafico originale $ G $ ha una colorazione valida $ \ chi $ , quindi possiamo Colorare la clique $ c_v $ come segue: il colore $ \ chi (V) $ appare $ p $ volte e tutti gli altri colori appaiono $ P + 1 $ volte. Puoi verificare che ogni vertice abbia esattamente $ p $ vicini dello stesso colore.

Viceversa, supponiamo che il nuovo grafico abbia una colorazione $ \ chi $ in cui ogni vertice ha al massimo $ P $ vicini dello stesso colore. Questo è possibile solo se ogni colore in $ c_v $ appare al massimo $ P + 1 $ volte, e Quindi alcuni colori $ \ chi '(v) $ appare $ p $ volte e il resto visualizza < Span Class="Math-Container"> $ P + 1 $ volte. Ciò implica che $ \ chi '(V)=chi (V) $ (dal momento che altrimenti $ V $ Avrerebbe $ P + 1 $ vicini con gli stessi colori) e inoltre che $ \ chi $ limitato ai vertici originali è una colorazione valida (nel senso abituale).