3
$\begingroup$

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 = System`Graph[{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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alexander Kartun-Giles Sep 4 '19 at 14:50
  • 1
    $\begingroup$ @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). $\endgroup$ – Szabolcs Sep 4 '19 at 14:53
  • 1
    $\begingroup$ @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? $\endgroup$ – Szabolcs Sep 4 '19 at 14:53
  • $\begingroup$ Ok thank you very much. $\endgroup$ – Alexander Kartun-Giles Sep 4 '19 at 15:04

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.