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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\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

Improve this answer
$\endgroup$
0
5
$\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.

Improve this answer
$\endgroup$
4
  • $\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$
    – apg
    Commented Sep 4, 2019 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
    Commented Sep 4, 2019 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
    Commented Sep 4, 2019 at 14:53
  • $\begingroup$ Ok thank you very much. $\endgroup$
    – apg
    Commented Sep 4, 2019 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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