9
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.