Question

a) Consider the graphs, G, H and I as shown below 5. 18 Marks] G: Н: (i) Find the chromatic polynomials T(G, k) and I(I, k) (ii) Find a formula relating I(G, k), r(H, k), and I'(I,k) (iii) Using the previous parts, or otherwise, find T(H, k')

Answer 1

B В" В' E A' I: C E" C' G:A Н: А D D' D'"' Let us name the vertices of the graphs G H, I as above shown. We want to find the number of coloring possible with k colours Consider graph G: The vertex A can be coloured with any of the given k colours. Then B can get (k-1) colours other than the colour of A, as A is adjacent to B. C also can get (k-1) colours other than the colour of A, as A is adjacent to C D also can get (k-1) colours other than the colour of A, as A is adjacent to D. However E can get (k-4) colours other than the colours of A, B, C, D, as E is adjacent to them. Thus the chromatic polynomial I(G, k) = k(k - 1)(k 1)(k - 1)(k - 4) = k(k - 1)3(k - 4)

Consider graph I: The vertex A' can be coloured with any of the given k colours. as A' is adjacent to B' Then B' can get (k-1) colours other than the colour of A', C' also can get (k-1) colours other than the colour of A', as A' is adjacent to C' D' also can get (k-1) colours other than the colour of A', as A' is adjacent to D'. Thus the chromatic polynomial I(I,k) = k(k - 1)(k - 1)(k - 1) = k(k - 1)3 The graph H is obtained from I by adoining a vertex E" and the edges B"E", C"E", D"E".| Thus the chromatic polynomial (k 3) - k(k 1)3 (k 3) ГІН, К) the chromatic polynomial I(I, k)