Chromatic Polynomial Small

Problem

Count the proper colorings of an undirected graph with k colors using inclusion-exclusion over edge subsets.

For each subset S of edges, count k^(number of connected components of (V, S)) with sign (-1)^|S|. Return the resulting integer, which is the chromatic polynomial evaluated at k. edges is a list of [u, v] pairs.

Hint

Inclusion-exclusion converts chromatic polynomial evaluation into component counting.

Test cases

case 1

in: [3,3,[[0,1],[1,2],[2,0]]]

expected: 6

case 2

in: [2,3,[[0,1],[1,2]]]

expected: 2

case 3

in: [3,4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]]

expected: 0

case 4

in: [4,3,[]]

expected: 64

case 5

in: [2,2,[[0,1]]]

expected: 2

Starter codePython

def chromatic_polynomial(k, n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor