3-Colouring Problem

computation

Definition

3-Colouring Problem

The 3-colouring problem is a decision problem.

Instance: an undirected graph $G=(V,E)$

Question: Does there exist a colouring of the vertices of $G$ with three colours such that adjacent vertices always have different colours?

NP-Membership

The 3-colouring problem is in NP. There are several equivalent ways to show this.

Let

$$R=\{((V,E),f)\mid f(v_i)\ne f(v_j)\text{ for all }{v}_i,v_j\in V\text{ with }[v_i,v_j]\in E\}.$$

Here, the certificate is a colouring function $f:V\to \{1,2,3\}$.

Why this proves NP-membership

A proposed colouring $f$ has size polynomial in $|V|$, and we can verify it in polynomial time by checking for every edge $[v_i,v_j]\in E$ that $f(v_i)\ne f(v_j)$.

Therefore, the 3-colouring problem has a polynomial-time verifier, so it belongs to NP.

A nondeterministic algorithm may guess one of three colours for each vertex and then check in polynomial time whether the resulting assignment is a valid 3-colouring.

Reductions

Reduction to SAT

Let $G=(V,E)$ be an instance of the 3-colouring problem with

$$V=\{v_1,\dots ,v_n\}.$$

For each vertex $v_i$ and each colour $c\in \{r,g,b\}$, introduce a propositional variable $a_i^c$.

The intended meaning is that $a_i^c$ is true exactly when vertex $v_i$ has colour $c$.

We define a reduction $R$ that maps $G$ to the SAT instance

$$R(G)={\phi }_G={\phi }_1\wedge {\phi }_2\wedge {\phi }_3,$$

where:

$${\phi }_1=\underset{1\le i\le n}{\bigwedge }(a_i^r\vee a_i^g\vee a_i^b)$$

ensures that every vertex gets at least one colour,

$${\phi }_2=\underset{1\le i\le n}{\bigwedge }(\neg (a_i^r\wedge a_i^g)\wedge \neg (a_i^r\wedge a_i^b)\wedge \neg (a_i^g\wedge a_i^b))$$

ensures that no vertex gets two different colours at the same time, and

$${\phi }_3=\underset{[v_i,v_j]\in E}{\bigwedge }(\neg (a_i^r\wedge a_j^r)\wedge \neg (a_i^g\wedge a_j^g)\wedge \neg (a_i^b\wedge a_j^b))$$

ensures that adjacent vertices do not receive the same colour.

Therefore, $G$ is 3-colourable if and only if ${\phi }_G$ is satisfiable.