# Chromatic Polynomial

**Problem .** Find the chromatic polynomial and chromatic number for the graph K_{3, 3}.

**Solution.** Chromatic polynomial for K3, 3 is given by λ(λ – 1)5.

Thus chromatic number of this graph is 2.

Since λ(λ – 1)5 > 0 first when λ = 2.

Here, only two distinct colours are required to colour K3, 3.

The vertices a, b and c may have one colours, as they are not adjacent.

Similarly, vertices d, e and f can be coloured in proper way using one colour.

But a vertex from {a, b, c} and a vertex from {d, e, f} both cannot have the same colour.

In fact every chromatic number of any bipartite graph is always 2.

**Problem . **Find the chromatic polynomial and hence the chromatic number for the graph shown below.

Solution. Since G is made up of components of G1, G2 and G3 where G1 = K3, G2 is a linear graph and G3 is an isolated vertex. Now G1 can be coloured in λ(λ – 1)(λ – 2) ways, G2 can be coloured in λ(λ – 1) ways and G3 is λ ways. Therefore, by the rule of product G can be coloured be

**λ(λ – 1)(λ – 2)λ(λ – 1)λ = λ ^{3}(λ – 1)^{2}(λ – 2).**