Let Gn be a graph which is obtained from the complete graph

Let Gn be a graph which is obtained from the complete graph Kn by deleting one edge.

Determine the chromatic polynomial ?Gn (?) and the chromatic number ?(Gn).

17. Let Gn be a graph which is obtained from the complete graph Kn by deleting one edge. Determine the chromatic polynomial (, (A) and the chromatic number (Gr.)

Solution

Chromatic number of Kn polynomial will be

PKn(k) = k(k-1)(k-2)....(k-n+1)

Since now only (n-1) colors are involved in the graph, the polynomial will be of (n-1) order, hence the chromatic polynomial will be

P(k) = k(k-1)(k-2)....(k-n+2)

The chromatic number of graph will become (n-1) since we have now two pair of vertices which don\'t have an edge and which can be colored with the same color, hence two vertices can share a same color and remaining (n-2) vertices requires (n-2) colors

Hence Chromatic Number = (n-2) + 1 = (n-1)