# Chromatic polynomial of a graph

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\$$.

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

This is , 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]

• planetmath lists $P(G,x)=\sum_{F \subset E}(-1)^{|F|} x^{|V|-r(F)}$ as a formula, which might be useful in (golfing) languages with a powerset builtin.
– ovs
Feb 18 at 17:32
• @ovs $r(F)$is the number of elements of any maximal cycle-free subset of $F$, which is equal to the number of vertices in $F$ minus the number of connected components of $F$ (seeing $F$ as a subgraph). Feb 21 at 3:32

# BQN, 625955 47 bytesSBCS

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↓𝕩)-.

# 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.

• Three one-byte savings: assigning e[-1] to a variable; 1:n*0->!1:n; renaming el to +. ATO! Apr 19 at 13:22

# 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!

• Snippets requiring input to be stored in a predefined variable aren't allowed by default; you can convert this into a pure function by replacing g with # and appending &. You can also save 1 byte by using infix notation (#~ChromaticPolynomial~x&) or returning a polynomial in Null (ChromaticPolynomial[#,]&) instead.
– att
Feb 17 at 21:09
• Better, ChromaticPolynomial alone works, returning a polynomial function in \[FormalX]. Try it online!
– att
Feb 17 at 21:10
• I am sorry, but I am fairly new to Mathematica. Why is this not considered a pure function? We do not store anything in g. We don't even define a variable g. I can call ChromaticPolynomial and provide any two arguments as a input. Feb 17 at 21:21
• Since builtin-graph objects are allowed as an input... Feb 17 at 21:23
• ChromaticPolynomial is a (built-in) function, but ChromaticPolynomial[g,x] does not yield the desired result when it's called on a single (graph) argument - it yields the desired value when g is replaced with the input (i.e. it's stored in g). See here or here for more on pure functions.
– att
Feb 17 at 21:35

# 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 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!

# 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!

• Functions don't need to be named, so you can remove the f= part and save 2 bytes. Feb 18 at 1:32
• @alephalpha But I can't call it then, can I? Feb 18 at 2:15
• You can call it like (lambda g:g.chromatic_polynomial())Graph(matrix([[0,0,0],[0,0,0],[0,0,0]])). You can also assign it to f and then call it, but lambda g:g.chromatic_polynomial() is already a function, so you don't need to count f=. Feb 18 at 2:21
• Well, yes, this is indeed a clever way to put it! Feb 18 at 2:21

# 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.

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]).

• I think you may replace sort by nub and save 1 byte. Apr 12 at 3:39

# Pari/GP, 87 bytes

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)