Vertex colouring and Brooks' theorem

Definition 7..1 (Vertex colouring)  

A vertex $k$-colouring of a graph $G$ is a function $c: V(G) \mapsto \{ 1,2,\cdots,k \}$, such that $c(x) \ne c(y)$ $\forall xy \in E(G)$.

We say $G$ is $k$-colourable if there is a $k$-colouring of $G$. Clearly $G$ is $k$-colourable iff it is $k$-partite.

Definition 7..2 (Chromatic number)  

The chromatic number $\chi(G)$ of a graph $G$ is the minimum $k$ for which $G$ is $k$-colourable.

Definition 7..3 (Greedy algorithm)  

Given an ordering $v_1,\cdots,v_n$ of $V(G)$, the greedy algorithm colours the vertices sequentially, giving vertex $v_i$ the smallest colour in $\{1,2,\cdots,n \}$ that is not in $c(\Gamma(v_i) \cap \{ v_1,v_2,\cdots,v_{i-1} \})$.

Clearly the number of colours used by the greedy algorithm depends on the order of the vertices. Furthermore given a colouring that uses only $\chi(G)$ colours it is possible to order the vertices so that the greedy algorithm will use no more than $\chi(G)$ colours.

Lemma 7..4 (Upper bound on $\chi(G)$)  

Given a graph $G$, $\chi(G) \le 1 + \Delta(G)$

Proof. Given a vertex $x$, then the greedy colouring algorithm will not give it a colour value more than $d(x) + 1$.

Therefore the greedy colouring algorithm colours all graphs with no more than $\Delta(G) + 1$ colours, so $\chi(G) \le 1 + \Delta(G)$.

$\qedsymbol$

Theorem 7..5 (Upper bound on $\chi(G)$)   $\chi(G) \le 1 + \max_{H \subseteq G} \delta(H)$ where $H$ ranges over all induced subgraphs of $G$ (including $G$).

Proof. We constructively describe a way of colouring $G$, by specifying a vertex order for the greedy colouring algorithm.

Let $n = \left\Vert V\right\Vert$. Let $H_n= G$. Let $x_n$ be a vertex in $H_n$ with degree $\delta(H_n)$. Certainly $\delta(G) < 1 + \max_{H \subseteq G} \delta(H)$. Let $H_{n-1} = H_n - \{ x_n \}$, $n > 1$.

The sequence $x_1,x_2,x_3,\cdots,x_n$ presents to the greedy colouring algorithm a series of vertices which have had at most $\max_{H \subseteq G} \delta(H)$ neighbours already coloured. Therefore at most $1 + \max_{H \subseteq G} \delta(H)$ colours can be used.

This bound is certainly exact for a complete graph.

$\qedsymbol$

Theorem 7..6 (Brooks)  

If $G$ is connected then $\chi(G) \le \Delta(G)$, unless $G$ is complete or $G$ is an odd cycle.

Proof. Certainly by the greedy algorithm $\chi(G) \le \Delta(G) + 1$.

Let $\Delta = \Delta(G)$.

If $\chi(G) = \Delta + 1$ then by 7.5 there is a subgraph $H$ of $G$ with $\delta(H) = \Delta$ ($H$ is $\Delta$-regular). But $G$ is connected and no vertex not in $H$ can connect to $H$, so $G = H$ and $G$ is $\Delta$-regular.

Now suppose $Delta = 1$. Then $G = K_2$. Suppose $\Delta = 2$. Then $G = C_3$. Therefore we need only consider $\Delta \ge 3$.

Sorry, but the rest of the proof will be omitted. The method is to take a vertex of degree $\Delta$ (the minimal degree) and as in the proof of Vizing's theorem, consider the components $H_ij$ of vertices coloured either $i$ or $j$ and the relationship its neighbours. By considering switching $i$,$j$ in these components one can show that the neighbours are pairwise joined.

$\qedsymbol$

Definition 7..7 (Chromatic polynomial)  

Let $G$ be a graph. Let $P_G(x)$ be the number of ways of colouring $G$ using $x$ colours.

Definition 7..8 (Notation for contracting edges $G/e$)  

Let $G$ be a graph. Let $e \in E(G)$. Then $G/e$ is the graph obtained by identifying the endpoints of $e$. That is if $e$ joins vertices $x,y$ then for each edge $yz$ join $z$ to $x$ if $z$ is not already joined to $x$. Then remove $y$.

Theorem 7..9 (Induction step on the chromatic polynomial)  

Let $e \in E(G)$. Then $P_G(x) = P_{G-e}(x) - P_{G/e}(x)$.

Proof. Let $e = uv$. The colourings $c$ of $G-e$ that are not colourings of $G$ are those with $c(u) = c(v)$, which are precisely the colourings of $P_{G/e}(x)$.

$\qedsymbol$

Corollary 7..10 (The chromatic polynomial is a polynomial)  

$P_G(x)$ is a polynomial in $x$. Furthermore, $P_G(x) = x^n - a_1 x^{n-1} + a_2 x^{n-2} + \cdots + (-1)^n a_n$ with $n = \left\Vert G\right\Vert$, $a_1 = e(G)$ and all $a_i \ge 0$.

Proof. By induction on $e(G)$. True for the empty graph. In general let $e \in E(G)$.

Now $P_{G-e}(x) = x^n - b_1 x^{n-1} + b_2 x^{n-2} + \cdots + (-1)^n b_n$, $P_{G/e}(x) = x^{n-1} - c_1 x^{n-2} + (-1)^(n-1) c_{n-1}$, where $n = \left\Vert G\right\Vert$, $b_1 = e(G) -1$ and all $b_i,c_i \ge 0$.

Now by the theorem, $P_G(x) = P_{G-e}(x) - P_{G/e}(x)$, so $P_G(x) = x_n - (b_1+1)x_{n-1} + (c_1 + b_2)x^{n-2} + \cdots + (-1)^n (b_n + c_{n-1})$, a polynomial of the same form.

$\qedsymbol$