# Tag Info

I think there's a straightforward transformation to graphs with colored edges, which can in turn be transformed into ordinary graphs. Given a CNF $\phi$ with clauses $c_i$ and variables $v_i$, construct a graph with vertices $c_i,v_i,\neg v_i$. Add black edges between each clause $c_i$ and each literal in it. Add a red edge between each variable $v_i$ and ...