Qual é o nome do problema? (gráfico de particionamento em três capas)

Eu queria saber se este problema tem um nome:

Dado um gráfico simples cujas bordas são de cor vermelha, azul e verde, , existe um-coloração vértice c : V → { B , R , G } de tal modo que cada extremidade tem um ponto de extremidade com a mesma cor?$G=(V,B\cup R\cup G)$$c:V\to \{B,R,G\}$

Além disso, isso é conhecido por ser NP-completo?

Isso também pode ser visto como um caso especial de CSP (ou uma generalização de 2SAT), em que cada restrição é uma disjunção de 2 variáveis ​​que podem assumir um dos três valores e não há duas restrições no mesmo par de variáveis.

$v$$v_R,v_B,v_G$ e cláusulas $\lnot v_R \lor \lnot v_B,\lnot v_R \lor \lnot v_G, \lnot v_B \lor \lnot v_G$. Isso garante que, no máximo, um dos$v_R,v_B,v_G$é verdade. Para cada aresta$(v,w)$ rotulado $R$, adicionaremos a cláusula $v_R \lor w_R$. Se houver uma coloração de vértice válida no seu sentido, ela se traduzirá claramente em uma solução dessa instância 2SAT. Por outro lado, qualquer solução para a instância 2SAT corresponde a uma coloração parcial na qual cada aresta é incidente em um vértice da mesma cor. Ao colorir os outros vértices arbitrariamente, obtemos uma coloração de vértice válida no seu sentido.