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 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.


Learned in MATH239.


Definition 2

A -colouring of a graph is an assignment of a colour to each vertex using one of colours, so that adjacent vertices have different colours. More precisely, if is a set of size , then a -colouring is a function such that for all . A graph that has a -colouring is called -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 is -colourable, and not -colourable for any .

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