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)

#todo Define#computer-science/algorithm/design/backtracking and#computer-science/algorithm/design/greedy versions

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.

#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)\in O(|V|)$$

Note, this trivial solution is the only solution in the case of complete graphs.

#todo By greedy colouring, $\chi (G)$ is bounded by $\Delta (G)+1$, where $\Delta$ is the maximum node degree .

Lower Bound §

something something cliques#todo

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.

#todo Algorithm

Applications §

• Conflict/Clashing Resolutions
  • Some people cannot be seated next to each other
  • Some subjects cannot be done at the same time

Resources §