Jaka jest nazwa problemu? (podział wykresu na trzy okładki)

Zastanawiałem się, czy ten problem ma nazwę:

Biorąc pod uwagę prosty wykres, którego krawędzie są w kolorze czerwonym, niebieskim i zielonym, $G=(V,B\cup R\cup G)$, czy jest kolorowanie wierzchołków $c:V\to \{B,R,G\}$ tak, że każda krawędź ma punkt końcowy tego samego koloru?

Czy jest to również znane jako NP-zupełne?

Można to również postrzegać jako szczególny przypadek CSP (lub uogólnienie 2SAT), gdzie każde ograniczenie jest rozłączeniem 2 zmiennych, które mogą przyjąć jedną z trzech wartości, i nie ma dwóch ograniczeń dla tej samej pary zmiennych.

Twój problem można rozwiązać w czasie liniowym, redukując do 2SAT. Dla każdego wierzchołka$v$ będziemy mieli trzy zmienne $v_R,v_B,v_G$ i klauzule $\lnot v_R \lor \lnot v_B,\lnot v_R \lor \lnot v_G, \lnot v_B \lor \lnot v_G$. Zapewniają to, że co najwyżej jeden$v_R,v_B,v_G$jest prawdziwy. Dla każdej krawędzi$(v,w)$ oznaczone $R$dodamy klauzulę $v_R \lor w_R$. Jeśli w twoim rozumieniu istnieje poprawne zabarwienie wierzchołków, to wyraźnie przekłada się to na rozwiązanie tego wystąpienia 2SAT. I odwrotnie, każde rozwiązanie wystąpienia 2SAT odpowiada częściowemu zabarwieniu, w którym każda krawędź pada na wierzchołek tego samego koloru. Kolorując pozostałe wierzchołki arbitralnie, uzyskujemy prawidłową kolorystykę wierzchołków w twoim znaczeniu.