# Counting k-colorings of a graph

Combinatorica can list all $$k$$-colorings of the vertices of a graph $$g$$, which is a coloring of the vertices with no two colors adjacent, and using no more than $$k$$-colors:

<< Combinatorica
<< GraphUtilities
g = SystemGraph[{1, 2, 3, 4, 5, 6}, {1 <-> 2, 3 <-> 4, 5 <-> 6}];
MinimumVertexColoring[ToCombinatoricaGraph@g, 2, All]


{{1, 2, 1, 2, 1, 2}, {1, 2, 1, 2, 2, 1}, {1, 2, 2, 1, 1, 2}, {1, 2, 2, 1, 2, 1}}

and IGraph can do the same, providing an example with minimum colors, without listing all:

IGKVertexColoring[g,2]


{{1, 2, 1, 2, 1, 2}}

Is there a way to list all the possible colourings without using Combinatorica? The IGraph package is much better and doesn't clash with system functions.

The function FindProperColorings is now in the Wolfram Function Repository, and it lists all the proper k-colorings of a graph.

https://resources.wolframcloud.com/FunctionRepository/resources/FindProperColorings

Counting k-colorings of a graph

Are you looking for https://en.wikipedia.org/wiki/Chromatic_polynomial of a graph? It can be computed with ChromaticPolynomial.

g = Graph[{1, 2, 3, 4, 5, 6}, {1 <-> 2, 3 <-> 4, 5 <-> 6}];

ChromaticPolynomial[g, 2]
(* 8 *)


There are twice as many as what Combinatorica returns because we can exchange colour 1 with colour 2 and get a distinct colouring.

• Thank you, this is valuable, but it doesn't list all the ways of doing it, only counting them. The Combinatorica function shows each coloring. Is there some way of doing this?
– apg
Sep 4, 2019 at 14:50
• @AlexanderKartun-Giles I did not implement it, but in principle it should be possible. IGraph/M uses a SAT formulation of the colouring, and Mathematica's SatisfiabilityInstances` should be able to list all solutions. What needs to be done first is to change the formulation so that it assigns only one colour to each vertex (currently it assigns multiple in such a way that any of those choices is acceptable). Sep 4, 2019 at 14:53
• @AlexanderKartun-Giles I won't have time right now, but why don't you post a feature request on GitHub so this doesn't get forgotten? Sep 4, 2019 at 14:53
• Ok thank you very much.
– apg
Sep 4, 2019 at 15:04