Question

Determine the chromatic polynomial Pk (G) for the following graphs:

Answer 1

14. (a) The following graph G is used to compute the chromatic polynomial P(G) : The above graph G is in the form of a tree with 4 vertices in it. P. (T) is a chromatic If a tree T is with n vertices, then P. (T) = k(k-1)n-1, where polynomial for a tree. The chromatic polynomial for the given graph G is as follows: P(G) = k (k – 1)"-1 = k(k – 1)-1 = k(k – 1) =k[k? – 1 – 3k(k-1)] =k(k-1-3k² + 3k) = k* - k – 3k’ +3k? P. (G)=K* – 3kº +3k? – k]

Therefore, the chromatic polynomial for the given graph is k* - 3k + 3k? -k. (b) The following graph G is used to compute the chromatic polynomial P.G): The above graph G is in the form of a complete graph with 4 vertices in it. If K, is a complete graph with n vertices, then P. (K,)=k(k-1)(k-2)...(k-n+1), where P. (K,) is a chromatic polynomial for a complete graph. The chromatic polynomial for the given graph G is as follows: P(Kn) = k(k-1)(k − 2)...(k - n +1) P(K) = k(k − 1)(k − 2)(k - 4 +1) = k(k 1)(k − 2)(k – 3) = k(k −1)[k? – 3k – 3k +6] = (k? – k)[k? – 6k+6]

= k4 - 6 +6k? - k +6k- 6k = k+ - 7k +12k? - 6k P (K) = k* – 7k? +12k– 6k] Therefore, the chromatic polynomial for the given graph is k* – 7kº +12k’– 6k. (c) The following graph G is used to compute the chromatic polynomial P.G): The above graph is neither a complete graph nor a tree. That's why divide the above graph into two parts from the red vertices. P(K2,k)

The chromatic polynomial for the given graph G is as follows: Complete graph(K) with 3 vertices x Tree(T) with 4 vertices P(K,,k) _ Pr(K3)xP;(T) P(K,,k) k(k-1)(k - 2)xk(k-1)4-1 k(k-1) k(k-1)(k-2)x k(k-1)3 k(k-1) = k(k − 1)(k − 2)(k – 1)? = k(k – 1)*(k − 2) = k[k? – 1 – 3k(k – 1)](k − 2) = k(k-13k+ 3k)(k − 2) = (k– 2k)(k-1-3k’ +3k) PK (G)= k® – 5k+ +9k’ – 7k? + 2k] Therefore, the chromatic polynomial for the given graph is k-5k+9k - 7k- + 2k (d) The following graph G is used to compute the chromatic polynomial P.(G) :

The above graph is neither a complete graph nor a tree. That's why divide the above graph into two parts from the red highlighted vertices. P(K2,k) The graph G is divide into two figures such as a tree with 5 vertices and a graph with 4 vertices. Tree (T) with 5 vertices x Graph with 4 vertices(G') P(K,k) A graph with 4 vertices can be further divided into two parts such that we obtain a tree with 4 vertices and a complete graph of 3 vertices.

Tree with 4 vertices - Complete graph with 3 vertices The chromatic polynomial for the given graph G is as follows: Tree(T) with 5 vertices x Graph with 4 vertices(G) P: (G)= P(K2,k) Tree(T) with 5 vertices x[Tree with 4 vertices - Complete graph with 3 vertices P(K,,k) _PL(T)x[P_(T) – P_(K)] P(K,,k) k(k –1)4x[(k(k – 1)--)(k(k – 1)(k − 2))] k(k-1) k(k – 1)* x[(k(k – 1)*) – (k(k − 1)(k − 2))] k(k-1) k(k-1)* x[(k(k – 1)) – (k(k − 1)(k − 2))] k(k-1) = kſk – 1)? ~[(k(k – 1)?)– (k(k − 1)(k –2))]

= k”(k – 1)ºx[(k – 1)2 – (k − 2)] = k” (k – 1) x[k? +1-2k – (k-2)] = k?(k – 1)? x[ 13 – 2k – k+1+2] = k”(k – 1)* x(k– 3k +3) = k?[k – 1 – 3k(k – 1)](k’ – 3k +3) = k·(k® – 1 – 3k’ +3k)(k’ – 3k +3) =(k– k– 3k* + 3k”) (k? – 3k +3) = k” – 3k + 3k” – k* +3k k? - 3k + 3k-k+ + 3k Therefore, the chromatic polynomial for the given graph is k? - 3kº +3k™ -k* +3k”. (e) The following graph G is used to compute the chromatic polynomial PxG):

The above graph is neither a complete graph nor a tree. That's why divide the above graph into two parts from the red highlighted vertices. P(K2,k) The graph G is divide into two figures such as a fully connected graph with 3 vertices and a graph with 4 vertices. Graph with 4 vertices(G) x Complete graph(K) with 3 vertices P(K2,k) A graph with 4 vertices can be further divided into two parts such that we obtain a tree with 4 vertices and a complete graph of 3 vertices.

P G')=Tree with 4 vertices - Complete graph with 3 vertices The chromatic polynomial for the given graph G is as follows: Graph with 4 vertices(G) x Complete graph(K) with 3 vertices P(K,,k) [Tree with 4 vertices - Complete graph with 3 vertices ] * Complete graph(K) with 3 vertices P(K,,k) _ [P;(T)-P_(K)] < P(K) P(K),k) [(k(k – 1)*+1) – (k(k − 1)(k − 2))]xk(k − 1)(k-2) k(k-1) [(k(k – 1)*)-(k(k − 1)(k − 2))]xk(k − 1)(k − 2) k(k – 1) =[(k(k – 1)")–(k(k − 1)(k–2))]<(k –2) = k/k – 1)(k − 2)(k – 1)2 – (k – 2)] = k{k – 1)(k − 2)[k? +1-2k -(k 2)] = k(k −1)k – 2)[k– 2k –k+1+2] = k(k – 1)(k – 2)[k? – 3k +3] =(k* – 3k² + 2k)(k? – 3k+3) PL (G)= K –6k* +14kº – 15k+6k|

Therefore, the chromatic polynomial for the graph is k-6k* +14k - 15k? +6k