Graph Colouring

Graph colouring an arbitrary graph is NP-Hard. Greedy works pretty well.

Greedy Algorithm to have the minimum amount of colours: (I am not sure this always works)

for each vertex v {
- colour v with the lowest colour not yet used by its neighbours
}

CS241E: Deciding whether an arbitrary graph can be coloured with $k$ colours is an NP-complete problem.

• There is no known polynomial time algorithm for finding a minimal graph colouring, and if one were to be found, it would be a major breakthrough in solving many other important problems. Therefore, there is no known polynomial time algorithm for optimal Register Allocation.

Some applications of graph colouring:

• Colouring a cartographic map: vertices are countries, two vertices are adjacent if the countries share a border; want to colour the map so that no two adjacent countries are the same colour. (Gets tricky in practice, since world geography is complicated by inclaves and exclaves.)
• Scheduling resources to jobs where there are conflicts: assigning aircrafts to flights, can’t use the same plane at the same time for two flights.
• Allocated registers in compilers: vertices are variables, edges denote variables needed at the same time. Can we fit all the variables into the number of available registers?
• Sudoku: vertices are cells, edges between cells that can’t have the same value due to Sudoku constraints; colouring is a valid Sudoku.

MATH239

Learned in MATH239.

Definitions

Definition 2

A $k$-colouring of a graph $G$ is an assignment of a colour to each vertex using one of $k$ colours, so that adjacent vertices have different colours. More precisely, if $C$ is a set of size $k$, then a $k$-colouring is a function $f:V(G)\to C$ such that $f(u)\ne f(v)$ for all $uv\in E(G)$. A graph that has a $k$-colouring is called $k$-colourable.

Theorems and Lemmas

Theorem 7.7.2

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

Theorem 7.7.3

The Complete Graph $K_n$ is $n$-colourable, and not $k$-colourable for any $k<n$.

4-Colour Theorem (Theorem 7.7.7)

Every Planar Graph is 4-colourable (can be coloured with at most 4 colours).

• Proved in 1976 by Appel and Haken, combining a 400-page proof plus 1,834 cases checked by a computer. One of the first computer-assisted proofs. A few flaws in the manual portion were fixed in the 80’s. The manual portion has since also been computer-verified, and the cases have been reduced to 633.

You should learn the 6-colour theorem and 5-colour theorem to get more familiar with graph proofs.

Solving this

• Bipartite Graph
• Interference Graph

Related

• Graph Matching