5
$\begingroup$

I'm starting in Wolfram Mathematica. I saw that MinimumVertexColoring [g] could be used to calculate the chromatic number of a graph, but MinimumVertexColoring [g] is part of the Combinatorica package, but it turns out that such a package is already obsolete.

Ref: http://mathworld.wolfram.com/MinimumVertexColoring.html

How can I compute the color number of a graph in version 11 of Mathematica?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ use the functions IGChromaticNumber and/or IGMinimumVertexColoring from Szabolcs's package IGraphM? $\endgroup$
    – kglr
    Commented Jan 10, 2019 at 8:07
  • $\begingroup$ Most of the graph theory functionality in Combinatorica is either built-in now or has a replacement in my IGraph/M package. I do not recommend Combinatorica anymore. If you come across something graph-related that is only possible with Combinatorica, let me know, and I will priority its inclusion in IGraph/M. $\endgroup$
    – Szabolcs
    Commented Jan 10, 2019 at 14:18

5 Answers 5

Reset to default
9
$\begingroup$

The IGraph/M package has an implementation of this.

Example:

<< IGraphM`

g = RandomGraph[{10, 20}]

enter image description here

Compute the chromatic number:

IGChromaticNumber[g]
(* 4 *)

Compute a minimum colouring:

IGMinimumVertexColoring[g]
(* {3, 1, 4, 2, 2, 4, 1, 3, 1, 2} *)

Visualize it:

IGVertexMap[ColorData[97], 
 VertexStyle -> IGMinimumVertexColoring, 
 Graph[g, VertexSize -> Large]]

enter image description here

This is by far the fastest implementation that exists for Mathematica, and is competitive with other systems. It is based on encoding the colouring problem into a Boolean satisfiability problem. (Thanks to Juho for the guidance on this!)

Computing the chromatic polynomial is harder than computing the chromatic number, so methods based on this won't work even for graphs of moderate size. Combinatorica is outdated and no longer easy to use, and its implementation is not efficient.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Something to look into. The following IGChromaticNumber@GraphData["HoffmanSingletonComplementGraph"] evaluated for over half an hour before I aborted it. $\endgroup$
    – Carl Woll
    Commented May 29, 2019 at 19:20
4
$\begingroup$

Without loading any packages:

g = RandomGraph[{30, 60}]
ResourceFunction["ChromaticNumber"][g]
Improve this answer
$\endgroup$
3
$\begingroup$

Very simple:

ChromaticPolynomial[g]
Improve this answer
$\endgroup$
2
$\begingroup$

There's a few options:

1. Combinatorica can still be used by first evaluating <<Combinatorica' (where the apostrophe is actually a grave accent. However, I've read that this can sometimes cause issues.

2. I came across the function ChromaticPolynomial in this answer: Chromatic number for "great circle" graph. Looking at the Applications section in the documentation, it seems that you can first calculate the chromatic polynomial as:

p[k] = ChromaticPolynomial[yourgraphhere, k]

and then find the one that provides the minimum number of colours:

MinValue[{k, k > 0 && p[k] >0}, k, Integers]

3. There is also a very neat graphing package called IGraphM that can do what you want, though I would recommend reading the documentation for that one.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Warning: don't try to run ChromaticPolynomial for larger graphs because it cannot be interrupted and you will need to force-quit the kernel. $\endgroup$
    – Szabolcs
    Commented Jan 10, 2019 at 14:29
  • $\begingroup$ @Szabolcs Ah, thanks! I haven't used it much and hadn't realized that. Your package looks to be the best solution to this by a wide margin. $\endgroup$
    – MassDefect
    Commented Jan 10, 2019 at 16:18
2
$\begingroup$

As this shows up quite early in the search results, I note that since version 13, you can use the built-in function VertexChromaticNumber.

PetersenGraph[5, 2] // VertexChromaticNumber
(* 3 *)

CompleteGraph[7] // VertexChromaticNumber
(* 7 *)

(FindVertexColoring gives a minimal coloring for a graph.)

Improve this answer
$\endgroup$

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.