Tag Info

We will reduce from 3COL, which is the following problem: Given a graph, is it 3-colorable? Given a graph $G=(V,E)$, we construct a new graph $G'$ on $V \times \{1,2,3\}$, whose edges are $$\{((i,a),(j,a)) \mid (i,j) \in E, a \in [3]\} \cup \{((i,a),(i,b)) \mid i \in V, 1 \leq a < b \leq 3 \}.$$ In words, we take three copies of $G$, and connect all ...