Question

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

Answer 1

i) To find the chromatic polynomial of G label it as follows

1 G 3 4 5 6 2 LO

We have to find the number of ways to color G with at most k colors.

Vertex 1 can be colored with k colors. Vertex 2 can be colored by any other color not used to color the vertex 1, hence there are k-1 colors. Vertices 3,4,5,6 cannot be colored by the previous two colors used are they are adjacent to 1 and 2. There are no other neighbors of 3,4,5,6 other than 1 and 2. Hence they can be colored by k-2 colors each.

Hence .

T(G, k)k(k 1) (k 2)

To find the chromatic polynomial of I label it as follows

1 I 2 5 4 Ln

We have to find the number of ways to color I with at most k colors.

Vertex 1 can colored by any of the k colors. Vertices 2,3,4,5 can be colored by any of the other k-1 colors.

Hence .

T(I,k) =k(k - 1)4

ii) To find a relation between the chromatic polynomials, let us look at how many ways H can be colored with at most k colors.

Label H as follows

1 H: 3 4 5 2 Ln

Case 1: Suppose vertices 1 and 2 are colored with the same color, then this graph looks like the graph I doubled on its base. Hence the number of such colorings is .

T(I, k

Case 2: Suppose vertices 1 and 2 get different colors, then we can assume there is an edge between without affecting the other colorings of this graph. Hence it looks looks like the graph G. Therefore the number of such colorings is

Г(G, R T.

Therefore by adding the two exclusive and exhaustive cases above, we have .

T(H, k (I, k) I(G, k)

iii)

T(H, k (I, k) I(G, k)

k(k 1)k(k- 1) (k 2)4-k(k 1)((k-1) (k-2))

.

k (k 1) (k4- 7k21k2- 29k 15)