¿Cuál es el nombre del problema? (gráfico de partición en tres portadas)

9

Me preguntaba si este problema tiene un nombre:

Dado un gráfico simple cuyos bordes son de color rojo, azul y verde, , ¿hay un color de vértice c : V { B , R , G } de modo que cada borde tenga un punto final con el mismo color?G=(V,BRG)c:V{B,R,G}

Además, ¿se sabe que esto es NP completo?


Esto también puede verse como un caso especial de CSP (o una generalización de 2SAT) donde cada restricción es una disyunción de 2 variables que podrían tomar uno de tres valores, y no hay dos restricciones en el mismo par de variables.

RB
fuente

Respuestas:

6

vvR,vB,vG¬vR¬vB,¬vR¬vG,¬vB¬vGvR,vB,vG(v,w)RvRwR

Yuval Filmus
fuente