13
\$\begingroup\$

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:

This 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 , 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]
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – ovs
    Feb 18 at 17:32
  • \$\begingroup\$ @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). \$\endgroup\$
    – alephalpha
    Feb 21 at 3:32

8 Answers 8

3
\$\begingroup\$

BQN, 62 59 55 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↓𝕩)-.
\$\endgroup\$
3
\$\begingroup\$

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.

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

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!

\$\endgroup\$
7
  • \$\begingroup\$ 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. \$\endgroup\$
    – att
    Feb 17 at 21:09
  • 1
    \$\begingroup\$ Better, ChromaticPolynomial alone works, returning a polynomial function in \[FormalX]. Try it online! \$\endgroup\$
    – att
    Feb 17 at 21:10
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 17 at 21:21
  • \$\begingroup\$ Since builtin-graph objects are allowed as an input... \$\endgroup\$ Feb 17 at 21:23
  • \$\begingroup\$ 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. \$\endgroup\$
    – att
    Feb 17 at 21:35
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ Functions don't need to be named, so you can remove the f= part and save 2 bytes. \$\endgroup\$
    – alephalpha
    Feb 18 at 1:32
  • \$\begingroup\$ @alephalpha But I can't call it then, can I? \$\endgroup\$ Feb 18 at 2:15
  • 1
    \$\begingroup\$ 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=. \$\endgroup\$
    – alephalpha
    Feb 18 at 2:21
  • \$\begingroup\$ Well, yes, this is indeed a clever way to put it! \$\endgroup\$ Feb 18 at 2:21
2
\$\begingroup\$

Charcoal, 104 bytes

⊞υθFυ«≔§ι⁰η≔⊟ιζ¿ζ«≔⊟ζδ≔⁻ζ⟦δ⮌δ⟧ζF⟦⟦ηζ⟧⟦⊖ηEζEκ⎇⁼μ⌈δ⌊δμ⟧⟧«⊞υκ⊞ικ»»»F⮌υ¿⊖Lι«≔⊟⊟ιη⊞ιE⊟⊟ι⁻κ§ηλ»⊞ιE⊕§θ⁰⁼κ§ι⁰I⊟θ

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:

⊞υθFυ«

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.

F⟦⟦ηζ⟧⟦⊖ηEζEκ⎇⁼μ⌈δ⌊δμ⟧⟧«

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.

»»»F⮌υ

Loop over the list of graphs in reverse order.

¿⊖Lι«

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

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

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

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

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

I⊟θ

Output the polynomial for the original graph.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ I think you may replace sort by nub and save 1 byte. \$\endgroup\$
    – alephalpha
    Apr 12 at 3:39
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.