SKEDSOFT

Graph Theory

Problem . Find the chromatic polynomial and chromatic number for the graph K3, 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).