Gráfico de variação de colorir

Question

Há variações do problema clássico de coloração do gráfico que o número de vizinhos na mesma cor é limitado, mas não zero (no problema original do limite é zero)?

Problema: Dado um gráfico $ g $ e dois inteiros $ c $ e $ P $ , é possível colorir os vértices de $ g $ com $ c $ cores como para cada vértice $ v $ com cor $ \ text {color} (v) $ ,

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

Answer 1

A definição que você está procurando é "coloração defeituosa" :

.

uma $ (k, d) $ -coring de um gráfico g é uma coloração de seus vértices com cores k, de modo que cada vizinho vinte.Tendo a mesma cor que o vértice v. Consideramos que k para ser um inteiro positivo (é inconseqüente considerar o caso quando k= 0) e d ser um inteiro não negativo.Portanto, $ (k, 0) $ -coring é equivalente à coloração adequada do vértice.

O número mínimo de cores K necessário para o qual G é $ (k, d) $ -colative é chamado de $ D $ -Defetivo número cromático, $ \ chi _ {d} (g) $ .

Answer 2

Eu não estou familiarizado com esta variante, mas ainda é np-completo para qualquer $ P $ .

Dado um gráfico $ g $ e um inteiro $ c $ , conecte-se a cada vértice $ v $ Uma clique $ c_v $ em $ (P + 1 ) C-1 $ vértices.

Se o gráfico original $ g $ tem uma coloração válida $ \ chi $ , então podemos Colorir a clique $ c_v $ da seguinte forma: a cor $ \ chi (v) $ aparece $ P $ vezes, e todas as outras cores aparecem $ p + 1 $ vezes. Você pode verificar se cada vértice tem exatamente $ P $ vizinhos da mesma cor.

Por outro lado, suponha que o novo gráfico tenha uma coloração $ \ chi $ em que cada vértice tem no máximo $ p $ vizinhos da mesma cor. Isso só é possível se cada cor na $ C_V $ aparece no máximo $ p + 1 $ vezes, e Então, alguma cor $ \ chi '(v) $ aparece $ p $ vezes, e o resto aparece < span class="contêiner matemático"> $ p + 1 $ vezes. Isso implica que $ \ chi '(v)=chi (v) $ (desde o contrário $ v $ teria $ p + 1 $ vizinhos com as mesmas cores) e, além disso, que $ \ chi $ restrito aos vértices originais é uma coloração válida (no sentido usual).