What is the name of the problem? (partitioning graph into three covers)

Question

I was wondering if this problem has a name:

Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G),ドル is there a vertex-coloring $c:V\to \{B,R,G\}$ such that every edge has an endpoint with the same color?

Also, is this known to be NP-complete?

---

This can also be viewed as a special case of CSP (or a generalization of 2SAT) where each constraint is a disjunction of 2 variables that could take one of three values, and there are no two constraints on the same variables-pair.

Answer 1

Your problem can be solved in linear time, by reduction to 2SAT. For each vertex $v$ we will have three variables $v_R,v_B,v_G$ and clauses $\lnot v_R \lor \lnot v_B,\lnot v_R \lor \lnot v_G, \lnot v_B \lor \lnot v_G$. These ensure that at most one of $v_R,v_B,v_G$ is true. For each edge $(v,w)$ labeled $R,ドル we will add the clause $v_R \lor w_R$. If there is a valid vertex coloring in your sense, then it clearly translates to a solution of this 2SAT instance. Conversely, any solution to the 2SAT instance corresponds to a partial coloring in which each edge is incident to a vertex with the same color. Coloring the other vertices arbitrarily, we obtain a valid vertex coloring in your sense.