Vertex Colouring and Chromatic Numbers

# Vertex Colouring and Chromatic Numbers

Imagine that we could take the vertices of a graph and colour or label them such that the vertices of any edge are coloured (or labelled) differently. This is what we recognize as vertex colouring

 Definition: A Good Vertex $k$-Colouring for $k \in \mathbb{Z^+}$ is a function $f: V(G) \to \{ 1, 2, 3, ... k\}$ for all $x, y \in V(G)$, whenever $\{ x , y \} \in E(G)$, $f(x) \neq f(y)$. A graph is said to be Vertex $k$-Colourable if it contains a good vertex $k$-colouring.

Note that we use the numbers $1, 2, ..., k$ to often represent colours.

Now let's look at the following graph for an example: Clearly, the graph $G$ can have its vertices coloured with $4$ colours since every edge contains two different coloured vertices. We can thus say that $G$ is $4$-colourable. Once again, we note that we can easily replace the colours with numbers or any other labels. The question then arises if the graph $G$ can have its vertices coloured with less colours. In fact, the vertices in $G$ can be coloured with exactly $3$ colours, so $G$ is $3$-colourable. Unfortunately, this graph is not $2$-colourable, so we say that minimum colourability of this graph is $3$. Often times determining this number is valuable in optimization problems. We will now define this number formally.

 Definition: The Chromatic Number of a graph $G$ denoted $\chi (G)$ is the smallest positive integer $k$ such that $G$ is vertex $k$-colourable (and thus $G$ has a good vertex $k$-colouring).

For our graph in the earlier example, we can say that $\chi (G) = 3$. Let's now look at some chromatic numbers for important graphs:

Graph Chromatic Number $\chi (G)$ Explanation
Complete Graphs $K_n$ $\chi (K_n) = n$ The chromatic number for complete graphs is n since by definition, each vertex is connected to one another. Hence each vertex must be coloured differently for a good colouring.
Even Cycle Graphs, $C_{2n}$ $\chi (C_{2n}) = 2$ For even cycle graphs, we start with one vertex and alternate using the two colours of our choice. We will only ever need at minimum $2$ colours.
Odd Cycle Graphs, $C_{2n+1}$ $\chi (C_{2n +1}) = 3$ For odd cycle graphs, we can also start at one vertex and alternate between two colours of our choice. We will eventually end up with one vertex that we cannot colour with the two colours we started with, hence, we will need a third colour.
Complete Bipartite Graphs, $K_{r,s}$ $\chi (K_{r, s}) = 2$ By definition, the complete bipartite graphs can have their vertices partitioned into two sets. We can thus take these two sets and colour them with $2$ distinct colours.
Tree graphs, $T$ $\chi (T) = 2$ We note that tree graphs are bipartite (and acyclic) allowing us to colour the vertices at minimum with 2 colours.
Path Graphs, $P_n$ $\chi (P_n) = 2$ Once again, path graphs are tree graphs which are bipartite.
Null Graphs, $N_n$ $\chi (N_n) = 1$ Null graphs contain no edges, so each vertex is isolated and can be coloured the same.