Question

(a) Find the chromatic polynomial PG(k) of the following graph G. Give 6. your answer in factorized form. (b) Write down x(G), the chromatic number of G (c) Without expanding Pc(k), find the coefficient of k28.

Answer 1

k-2 k-2 k-2 k-1 d k-1 k-1 k- k-2 k-1 k- k-2 E B k-2 k-2 4x4 3x4 P(k)k(k-1 (k-2) G k-2 k-2 A k-29D k-1 ok-2 k- Rk-2 k-1k-1 k-1 k-1 k-1 k-2 k-2 k-2 To understand the chromatic polynomial consider the potion of the graph denoted by the vertices OABCEFHD

we start colouring the vertices with k-colours. Then suppose we first colour O with any of Suppose the k colours, then vertex A can be coloured with k-1 colours and vertex B can be coloured with k-2 colours. Vertex C can be coloured with k-1 colours as it can not get the same colour as B. Vertex D can be coloured with k-1 colours. Vertex F can be coloured with k-2 colours as it has to be different from A and B' s colour. Similarly, vertex E can be coloured with k-2 colours as it has to be different from C and Fs colour. Vertex H can be coloured with k-2 colours as it has to be different from D and Fs colour This can be done for the other three sinmilar types, hence P (k) k(k 1)3 (k 2)4(k - 1)3(k 2)4(k -1)3 (k 2)4(k 1)3(k 2)4 - k(k - 1)12 (k - 2)16 the chromatic polynomial consists of vwwwod b) As described above we can see that the chromatic polynomial has factor k, k-1, k-2, (that is k-(3-1)), thus, with 3 colours the graph can be coloured. So x(G) 3 c) Coefficient of k28 in Pg(k) is -(12 16 x 2) = -40