2-Colouring Problem

computation

Definition

2-Colouring Problem

The 2-colouring problem is a decision problem that asks whether the vertices of a graph can be coloured with at most 2 colours so that no two adjacent vertices have the same colour.

Instance: graph $G$
Question: Does $G$ admit a proper colouring with 2 colours?

A graph is 2-colourable if and only if it is bipartite.

Reduction

Many-One Reduction to 2-SAT

Let $G=(V,E)$ be an instance of 2-colouring, i.e. $G$ is an undirected graph with vertices $V=\{v_1,v_2,\dots ,v_n\}$ and edges $E$.

We construct an instance ${\phi }_G$ of 2-SAT with variables $x_1,\dots ,x_n$ of form:

$${\phi }_G=\underset{[v_i,v_j]\in E}{\bigwedge }\left((x_i\vee x_j)\wedge (\neg x_i\vee \neg x_j)\right)$$

where $x_i=\text{true}$ means that vertex $v_i$ is coloured with the first colour, and $x_i=\text{false}$ means that it is coloured with the second colour.

For every edge $[v_i,v_j]\in E$, the two clauses force $x_i$ and $x_j$ to have different truth values. Therefore, adjacent vertices receive different colours.

Conversely, if $G$ is 2-colourable, then the two colours induce a truth assignment that satisfies every clause in ${\phi }_G$.

Thus, $G$ is 2-colourable if and only if ${\phi }_G$ is satisfiable, so 2-colouring many-one reduces to 2-SAT.

Completeness ( $\Rightarrow$)

If $G$ is 2-colourable, then assign each variable $x_i$ according to the colour of $v_i$. Every edge connects vertices of different colours, so every clause in ${\phi }_G$ is satisfied.

Soundness ( $\Leftarrow$)

If ${\phi }_G$ is satisfiable, then for every edge $[v_i,v_j]\in E$, the clauses $(x_i\vee x_j)$ and $(\neg x_i\vee \neg x_j)$ force $x_i$ and $x_j$ to have different truth values. Hence adjacent vertices receive different colours, so $G$ is 2-colourable.