Chromatic polynomial of a graph

Question

Given a undirected graph \$G\$ and a integer \$k\$, how many \$k\$-coloring does the graph have?

Here by a \$k\$-coloring, we mean assigning one of the \$k\$ colors to each vertex of the graph, such that no two vertices connected by an edge have the same color. For example, the following graph can be 3-colored in 12 different ways:

Let \$P(G,k)\$ denotes the number of \$k\$-coloring of the graph \$G\$. For example, \$P(G, 3) = 12\$ for the graph above.

\$P(G,k)\$ is in fact a polynomial in \$k\$, which is known as the chromatic polynomial. For example, the chromatic polynomial of the graph above is \$k^4-4k^3+5k^2-2k\$.

This can be shown using the deletion–contraction formula, which also gives a recursive definition of the chromatic polynomial.

The following proof is taken from Wikipedia:

For a pair of vertices \$u\$ and \$v\$, the graph \$G/uv\$ is obtained by merging the two vertices and removing any edges between them. If \$u\$ and \$v\$ are adjacent in \$G\$, let \$G-uv\$ denote the graph obtained by removing the edge \$uv\$. Then the numbers of \$k\$-colorings of these graphs satisfy: $$P(G,k)=P(G-uv, k)- P(G/uv,k)$$ Equivalently, if \$u\$ and \$v\$ are not adjacent in \$G\$ and \$G+uv\$ is the graph with the edge \$uv\$ added, then $$P(G,k)= P(G+uv, k) + P(G/uv,k)$$ This follows from the observation that every \$k\$-coloring of \$G\$ either gives different colors to \$u\$ and \$v\$, or the same colors. In the first case this gives a (proper) \$k\$-coloring of \$G+uv\$, while in the second case it gives a coloring of \$G/uv\$. Conversely, every \$k\$-coloring of \$G\$ can be uniquely obtained from a \$k\$-coloring of \$G+uv\$ or \$G/uv\$ (if \$u\$ and \$v\$ are not adjacent in \$G\$).

The chromatic polynomial can hence be recursively defined as

• \$P(G,x)=x^n\$ for the edgeless graph on \$n\$ vertices, and
• \$P(G,x)=P(G-uv, x)- P(G/uv,x)\$ for a graph \$G\$ with an edge \$uv\$ (arbitrarily chosen).

Since the number of \$k\$-colorings of the edgeless graph is indeed \$k^n\$, it follows by induction on the number of edges that for all \$G\$, the polynomial \$(G,x)\$ coincides with the number of \$k\$-colorings at every integer point \$x=k\$.

Task

Given a undirected graph \$G\$, outputs its chromatic polynomial \$P(G, x)\$.

This is code-golf, so the shortest code in bytes wins.

Input

You can take input in any reasonable format. Here are some example formats:

• an adjacency matrix, e.g., [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]];
• an adjacency list, e.g., {1:[2,3],2:[1,3,4],3:[1,2],4:[2]};
• a vertex list along with an edge list, e.g., ([1,2,3,4],[(1,2),(2,3),(3,1),(2,4)]);
• a built-in graph object.

You may assume that the graph has no loop (an edge connecting a vertex with itself) or multi-edge (two or more edges that connect the same two vertices), and that the number of vertices is greater than zero.

Output

You can output in any reasonable format. Here are some example formats:

• a list of coefficients, in descending or ascending order, e.g. [1,-4,5,-2,0] or [0,-2,5,-4,1];
• a string representation of the polynomial, with a chosen variable, e.g., "x^4-4*x^3+5*x^2-2*x";
• a function that takes an input \$n\$ and gives the coefficient of \$x^n\$;
• a built-in polynomial object.

Testcases:

Input in adjacency matrices, output in polynomial strings:

[[0,0,0],[0,0,0],[0,0,0]] -> x^3
[[0,1,1],[1,0,1],[1,1,0]] -> x^3-3*x^2+2*x
[[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]] -> x^4-3*x^3+3*x^2-x
[[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]] -> x^4-4*x^3+5*x^2-2*x
[[0,1,1,1,1],[1,0,1,1,1],[1,1,0,1,1],[1,1,1,0,1],[1,1,1,1,0]] -> x^5-10*x^4+35*x^3-50*x^2+24*x
[[0,1,1,0,1,0,0,0],[1,0,0,1,0,1,0,0],[1,0,0,1,0,0,1,0],[0,1,1,0,0,0,0,1],[1,0,0,0,0,1,1,0],[0,1,0,0,1,0,0,1],[0,0,1,0,1,0,0,1],[0,0,0,1,0,1,1,0]] -> x^8-12*x^7+66*x^6-214*x^5+441*x^4-572*x^3+423*x^2-133*x
[[0,0,1,1,0,1,0,0,0,0],[0,0,0,1,1,0,1,0,0,0],[1,0,0,0,1,0,0,1,0,0],[1,1,0,0,0,0,0,0,1,0],[0,1,1,0,0,0,0,0,0,1],[1,0,0,0,0,0,1,0,0,1],[0,1,0,0,0,1,0,1,0,0],[0,0,1,0,0,0,1,0,1,0],[0,0,0,1,0,0,0,1,0,1],[0,0,0,0,1,1,0,0,1,0]] -> x^10-15*x^9+105*x^8-455*x^7+1353*x^6-2861*x^5+4275*x^4-4305*x^3+2606*x^2-704*x

Input in vertex lists and edge lists, output in descending order:

[1,2,3], [] -> [1,0,0,0]
[1,2,3], [(1,2),(1,3),(2,3)] -> [1,-3,2,0]
[1,2,3,4], [(1,2),(2,3),(3,4)] -> [1,-3,3,-1,0]
[1,2,3,4], [(1,2),(1,3),(2,3),(2,4)] -> [1,-4,5,-2,0]
[1,2,3,4,5], [(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)] -> [1,-10,35,-50,24,0]
[1,2,3,4,5,6,7,8], [(1,2),(1,3),(1,5),(2,4),(2,6),(3,4),(3,7),(4,8),(5,6),(5,7),(6,8),(7,8)] -> [1,-12,66,-214,441,-572,423,-133,0]
[1,2,3,4,5,6,7,8,9,10], [(1,3),(1,4),(1,6),(2,4),(2,5),(2,7),(3,5),(3,8),(4,9),(5,10),(6,7),(6,10),(7,8),(8,9),(9,10)] -> [1,-15,105,-455,1353,-2861,4275,-4305,2606,-704,0]

Answer 1

BQN, 62 59 55 47 bytes^SBCS

Takes a vertex list 𝕨 on the left and an edge list 𝕩 on the right. Returns coefficients in descending order.

{×≠𝕩?(𝕨𝕊1↓𝕩)-0∾(1↓𝕨)𝕊⍷∧¨1↓𝕩-(-´⊑𝕩)×𝕩=⊑⊑𝕩;1∾0¨𝕨}

Run online!

This is a recursive function based on the deletion-contraction formula.

If the edge list is empty (¬×≠𝕩) the polynomial 1 0 ... 0 with as many zeros as there are vertices is returned. (1∾0¨𝕨)

Otherwise:

• Pick \$uv\$ as the first edge in the list 𝕩, replace all occurences of \$u\$ with \$v\$: 𝕩-(-´⊑𝕩)×𝕩=⊑⊑𝕩.
• Remove the edge \$uv\$ (now \$vv\$), sort each edge and remove duplicate edges generated by merging \$u\$ and \$v\$: ⍷∧¨1↓.
• Recursively call the function with this new edge list and and a vertex list with one less vertex: (1↓𝕨)𝕊. (Technically we would want to remove \$u\$ from 𝕨, but as we only care about the length of the vertex list, removing the first one achieves the same). This is \$P(G/uv, x)\$.
• Because the recursive call got one less vertex, the resulting polynomial will have one degree too few. By prepending a zero this can be fixed: 0∾.
• Recursively call the function on \$G-uv\$ and subtract the previous result from this: (𝕨𝕊1↓𝕩)-.

Answer 2

Haskell, 102 bytes

Port of my BQN answer.

import Data.List
n!([u,v]:e)=zipWith(-)(n!e)$0:tail n!nub[sort$take 2$(r++[v])\\[u]|r<-e]
n!_=1:(0<$n)

Try it online!

I feel like there should be a shorter way to replace \$u\$ with \$v\$ in a list (currently take 2$(r++[v])\\[u]).

Answer 3

R, 111 108 bytes

f=\(n,e,`+`=el)`if`(length(e),f(n,x<-e[-1])-f(n-1,unique(Map(\(i)sort(ifelse(+e+1-i,i,+e+2)),x))),c(!1:n,1))

Attempt This Online!

Takes input as the number of vertices n and list of edges e. Outputs a vector of coefficients in ascending order.

Thanks to pajonk for -3 bytes.

Answer 4

Wolfram Language (Mathematica), 24 bytes

#~ChromaticPolynomial~x&

Try it online!

We create a pure function for the built-in Mathematica function ChromaticPolynomial. We make use of infix notation.

If we need to allow adjacency matrices we can parse them to a graph using AdjacencyGraph. Thus we need more bytes in this case.

Edit: Thanks to att for guiding me to the correct solution!

Answer 5

Python3, 668 bytes

from copy import*
R=lambda x:x[0]*R(x[1:])if x else 1
e=lambda g:[(i,[*g[i]][0])for i in g if g[i]][0]
T=set.remove
def r(g,e):
 g=deepcopy(g);T(g[e[0]],e[1])
 if e[1]in g:g[e[1]]={i for i in g[e[1]]if i!=e[0]}
 return g
def m(g,e):
 g=deepcopy(g);T(g[e[0]],e[1])
 if e[1]in g:g[e[1]]={i for i in g[e[1]]if i!=e[0]}
 for i in g.get(e[1],[]):
  if i in g:g[i].add(e[0])
 if e[1]in g:del g[e[1]]
 return{x:{[i,e[0]][i==e[1]]for i in g[x]}for x in g}
def f(g,s=[]):
 if not any(g.values()):yield(s,len(g));return
 yield from f(r(g,E:=e(g)),s+[1]);yield from f(m(g,E),s+[-1])
def F(g):
 d={}
 for a,b in f(g):d[b]=d.get(b,0)+R(a)
 return[*d.values()]+[0]*(len(g)-len(d)+1)

Try it online!

Answer 6

SageMath, 35 33 bytes

lambda g:g.chromatic_polynomial()

Try it here!

The function f takes a built-in graph object as an argument and calculates its chromatic polynomial. However, it is fairly simple to parse a matrix directly into a sage graph object as follows.

Graph(matrix([[0, 1, 1], [1, 0, 1], [1, 1, 0]]))

In this case we would need more bytes.

Notice the difference to my post for Mathematica. In Mathematica we call a function and provide the graph as an argument. Here, the graph object's interface specifies the function chromatic_polynomial, which needs more code.

Thanks to alephalpha we can save 2 bytes!

Answer 7

Charcoal, 104 bytes

⊞υθＦυ«≔§ι⁰η≔⊟ιζ¿ζ«≔⊟ζδ≔⁻ζ⟦δ⮌δ⟧ζＦ⟦⟦ηζ⟧⟦⊖ηＥζＥκ⎇⁼μ⌈δ⌊δμ⟧⟧«⊞υκ⊞ικ»»»Ｆ⮌υ¿⊖Ｌι«≔⊟⊟ιη⊞ιＥ⊟⊟ι⁻κ§ηλ»⊞ιＥ⊕§θ⁰⁼κ§ι⁰Ｉ⊟θ

Try it online! Link is to verbose version of code. Takes input as a pair of the number of vertices and a list of edges and outputs the polynomial as a list of coefficients in ascending order. Explanation:

⊞υθＦυ«

Start processing with the input graph.

≔§ι⁰η≔⊟ιζ

Get the number of vertices and list of edges of this graph.

¿ζ«

If the graph still has edges, then...

≔⊟ζδ

Remove an edge from the list.

≔⁻ζ⟦δ⮌δ⟧ζ

Remove any other duplicate copies of that edge from the list.

Ｆ⟦⟦ηζ⟧⟦⊖ηＥζＥκ⎇⁼μ⌈δ⌊δμ⟧⟧«

Loop over the graph with the edge removed and the graph with the edge merged.

⊞υκ⊞ικ

Push each graph both to the list of graphs to process but also to the graph that is being processed.

»»»Ｆ⮌υ

Loop over the list of graphs in reverse order.

¿⊖Ｌι«

If this graph had to be split into two simpler graphs, then...

≔⊟⊟ιη⊞ιＥ⊟⊟ι⁻κ§ηλ

... push the difference between the two polynomials from the simpler graphs to this graph, ...

»⊞ιＥ⊕§θ⁰⁼κ§ι⁰

... otherwise push the polynomial for a trivial graph to this graph.

Ｉ⊟θ

Output the polynomial for the original graph.

Answer 8

Pari/GP, 87 bytes

A port of ovs's Haskell answer. Make sure to upvote that answer as well!

f(n,e)=if(e,[u,v]=e[1];-f(n[^1],Set([Set([if(w-u,w,v)|w<-r])|r<-e=e[^1]]))+f(n,e),x^#n)

Try it online!

Answer 9

Python + sympy, 458 bytes

A Port of @ovs's Haskell answer.

---

Golfed version. Attempt this online!

from sympy import*
def f(n,e):
    if e:
        u,v=e[0]
        w=[N for N in n if N!=u]
        E=[]
        for d in e[1:]:
            if u in d and v in d:
                continue
            elif u in d:
                E.append([v if N == u else N for N in d])
            else:
                E.append(d)
        E= [list(i) for i in set(tuple(sorted(s)) for s in E)]
        return -f(w,E)+f(n,e[1:])
    else:
        return symbols('x')**len(n)

Ungolfed version. Attempt this online!

from sympy import symbols

x = symbols('x')

def f(n, e):
    if e:
        u, v = e[0]
        n_without_u = [node for node in n if node != u]

        # Generate new edges after merging u and v
        new_edges = []
        for edge in e[1:]:
            if u in edge and v in edge:
                continue  # remove edge if it contains both u and v
            elif u in edge:
                new_edges.append([v if node == u else node for node in edge])
            else:
                new_edges.append(edge)

        # Remove any potential duplicate edges
        new_edges = [list(item) for item in set(tuple(sorted(sub)) for sub in new_edges)]
        
        return -f(n_without_u, new_edges) + f(n, e[1:])
    else:
        return x**len(n)

test_cases = [
    [[1,2,3], []],
    [[1,2,3], [[1,2],[1,3],[2,3]]],
    [[1,2,3,4], [[1,2],[2,3],[3,4]]],
    [[1,2,3,4], [[1,2],[1,3],[2,3],[2,4]]],
    [[1,2,3,4,5], [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]]],
    [[1,2,3,4,5,6,7,8], [[1,2],[1,3],[1,5],[2,4],[2,6],[3,4],[3,7],[4,8],[5,6],[5,7],[6,8],[7,8]]],
    [[1,2,3,4,5,6,7,8,9,10], [[1,3],[1,4],[1,6],[2,4],[2,5],[2,7],[3,5],[3,8],[4,9],[5,10],[6,7],[6,10],[7,8],[8,9],[9,10]]]
]

for case in test_cases:
    print(f"{case} -> {f(case[0], case[1])}")