COCS5313 Program-2 Due: 3/27/2013 Chromatic Polynomial Computation. (Bonus Program for up to 20 Bonus Points) Task: Write a program to calculate the Chromatic polynomial of a given undirected graph. Requirements: 1. Each polynomial calculated will be printed out according to the following format: a. Degree: 4 b. Coefficients: 1 -6 11 -6 (In descending order of powers) 2. For each input undirected graph, the following will be output: a. The input graph: (in terms of edges) b. Its Chromatic polynomial as indicated in (1) above. Suggestions: 1. Use the following Fundamental Reduction Theorem: Pick any edge, say k. Let this edge connect two vertices, a and b. Define two new graphs, G1 and G2, from the current graph G as follows: G1: Delete the edge k only, leaving everything else. G2: Delete the edge k and combine the two vertices a and b. So, either vertex must disappear for good. In the process, any edge incident to this disappearing vertex must be made incident to the surviving vertex instead if it is not so incident already. Then, P(G,x) = P(G1,x) - P(G2,x) 2. Repeatly apply the above Theorem and hence delete an edge until in the worst case there is no edge left in every graph you get. Note: P(G,x) = x**n if G is a graph with n vertices and no edge. P(G,x) = x*(x-1)**(n-1) if G is a star with n vertices and n-1 edges such that exactly one vertex is adjacent to every other vertex and no other adjacency exists. Inputs: Use the following three cases: (1,2) (2,3) (3,4) (4,1) // Coefficients of the polynomial of degree 4: (1, -4, 6, -3) (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) // Coefficients of the Polynomial of Degree 4: (1, -6, 11, -6) (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) (4,5) (4,6) (4,7) (5,6) (5,7) Degree: 7