Wie heißt das Problem? (Aufteilung des Diagramms in drei Umschläge)

9

Ich habe mich gefragt, ob dieses Problem einen Namen hat:

Bei einem einfachen Graphen, dessen Kanten rot, blau und grün gefärbt sind, , gibt es eine Scheitelpunktfärbung c : V { B , R , G }, so dass jede Kante einen Endpunkt hat mit der gleichen Farbe?G=(V,BRG)c:V{B,R,G}

Ist dies auch als NP-vollständig bekannt?


Dies kann auch als Sonderfall von CSP (oder einer Verallgemeinerung von 2SAT) angesehen werden, bei dem jede Einschränkung eine Disjunktion von 2 Variablen ist, die einen von drei Werten annehmen können, und es gibt keine zwei Einschränkungen für dasselbe Variablenpaar.

RB
quelle

Antworten:

6

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

Yuval Filmus
quelle