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
Question: Does 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 be an instance of 2-colouring, i.e. is an undirected graph with vertices and edges .

We construct an instance of 2-SAT with variables of form:

where means that vertex is coloured with the first colour, and means that it is coloured with the second colour.

For every edge , the two clauses force and to have different truth values. Therefore, adjacent vertices receive different colours.

Conversely, if is 2-colourable, then the two colours induce a truth assignment that satisfies every clause in .

Thus, is 2-colourable if and only if is satisfiable, so 2-colouring many-one reduces to 2-SAT.

Completeness ( )

If is 2-colourable, then assign each variable according to the colour of . Every edge connects vertices of different colours, so every clause in is satisfied.

Soundness ( )

If is satisfiable, then for every edge , the clauses and force and to have different truth values. Hence adjacent vertices receive different colours, so is 2-colourable.