# How to reduce 2-coloring to 2-SAT

Let $G=(V,E)$ be an undirected graph in which $V = \{v_1,v_2,\dots,v_n\}$.

I need to describe a reduction from the 2-coloring problem to the 2-SAT problem (in polynomial time).

I thought of splitting each vertex $v_i$ into $v_i^*$ and $v_i^{**}$, one for each color. Then I was thinking about making for each edge $(u,v)\in E$, two correspond literals: $(u^* \lor v^*)$ and $(u^{**} \lor v^{**})$.

I know I'm on the right track but I can't prove it.

any ideas?

If all you require is a polynomial-time reduction, then test in polynomial time if $G$ is $2$-colourable. If it is, map it to the formula $X$; if it isn't, map it to $X\land\lnot X$.

Consider a graph $G=(V,E)$.

Given a node $v_i \in V$ as you did, you can split into 2 variables $v_{i,1}$ and $v_{i,2}$ representing the 2 colors.

Now you just need 3 kind of clauses:

• each node cannot have more than one color
• Each node must have assigned a color
• $\forall$ edge $(u,v) \in E$, $u$ and $v$ cannot have the same color.

Then you just have to write it as a conjunction of clauses, where each clause is a disjunction of 2 literals.

G admits a 2-coloring $\iff$ there exists a truth assignment that satisfy the formula.