Graph Colouring Problem

The graph colouring problem is an algorithmic problem that asks if it is possible to colour the nodes in a graph such that no adjacent nodes have the same colour. It has a variety of applications in conflict resolutions. A graph that can be coloured in this way is said to admit a colouring and is a coloured graph.

Info Techinically

There are different types of colouring, such as edge colouring and face colouring but I choose to talk about proper vertex colouring:

• Vertex: Vertices/nodes are coloured
• Proper: Same colours cannot be adjacent (adjacent depends on the structure)

Problem Description(s) §

• Let $G$ be a simple graph $G$
• Let $C=\{1,2,3,\dots n\}$ be a set of $n$ colours which each integer in $C$ mapped to a unique colour.
• $v\text{.colour}=1$ means the node $v$ has been mapped to $1\in C$

Decision Version §

Is it possible to assign a colour to every node $v$ in $G$ such that no two adjacent nodes share the same colour?

$$\forall u\in \text{adj}(v),v\text{.colour}\ne u\text{.colour}$$

Optimisation Version §

Find the chromatic number $\chi (G)$ of $G$. That is, find the least amount of colours needed to admit a proper vertex colouring of $G$, where every node is coloured and no two adjacent nodes share the same colour.

This is NP-Complete.

#todo Write the question description better.

Bounds §

Upper Bound §

Since a trivial solution is to have every node have a different colour, an upper bound for $\chi (G)$ is:

$$\chi (G)\le |V|$$

Note, this trivial solution is the only solution in the case of complete graphs, i.e. $\chi (G)=|V|$

Coloured Graph.md

If we look only at planar graphs, then a much tighter upper bound is given by the four colour theorem:

Another, more general upper bound is given by Brook’s theorem:

Lower Bound §

Bounded §

Thus, for any connected graph that is not weakly perfect, nor odd-cycled, the chromatic number is bounded by Brook’s theorem and the clique number:

$$|V{|}_{K_n}\le \chi (G)\le {\text{deg}}_{\max }(v)$$

Solutions §

Greedy Approach §

A greedy algorithm can be used to attempt a graph colouring, by trying to colour the entire graph a certain colour, except for when it would result in two adjacent nodes having the same colour. In this case, change the colour of those nodes, and attempt to do it again for all of these problematic nodes. Repeat until no such problematic nodes exist.

A greedy graph colouring will always be correct, but (in most cases), is not optimal. Optimality heavily depends on the order of nodes traversed through when colouring the graphs.

The procedure is (roughly):

Let $G=(V,E)$ be the graph to be coloured.

1. Initialise $C=\{c_1\}$, the set of colours, with length $i=1$
2. For each uncoloured node $v$:
   1. For each colour $c$ in $C$:
      1. Colour $v$ with $c$ if it does not create any conflicts
   2. Else, increase $i$ by 1 and add a new colour $c_i$ . Colour $v$ with $c_i$

#todo Define#computer-science/algorithm/design/backtracking

Applications §

• Allocation problems
  • Some people cannot be seated next to each other
  • Some subjects cannot be done at the same time
• The map colouring problem is a special case of the graph colouring problem, (restricted to planar graphs)

Resources §