# How can I compute the chromatic number of a graph?

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.

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

• use the functions IGChromaticNumber and/or IGMinimumVertexColoring from Szabolcs's package IGraphM? – kglr Jan 10 '19 at 8:07
• 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. – Szabolcs Jan 10 '19 at 14:18

The IGraph/M package has an implementation of this.

Example:

<< IGraphM

g = RandomGraph[{10, 20}] 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,
VertexStyle -> IGMinimumVertexColoring,
Graph[g, VertexSize -> Large]] 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.

• Something to look into. The following IGChromaticNumber@GraphData["HoffmanSingletonComplementGraph"] evaluated for over half an hour before I aborted it. – Carl Woll May 29 '19 at 19:20

Very simple:

ChromaticPolynomial[g]


g = RandomGraph[{30, 60}]
ResourceFunction["ChromaticNumber"][g]


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.

• Warning: don't try to run ChromaticPolynomial for larger graphs because it cannot be interrupted and you will need to force-quit the kernel. – Szabolcs Jan 10 '19 at 14:29
• @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. – MassDefect Jan 10 '19 at 16:18