# 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, 2019 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. Jan 10, 2019 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[97],
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. May 29, 2019 at 19:20

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


Very simple:

ChromaticPolynomial[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. Jan 10, 2019 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. Jan 10, 2019 at 16:18