Vertex-coloring a graph

I am seeking the equivalent of MinimumVertexColoring[g] in Mathematica 12. I've been unsuccessful with either of these options to access old code:

<< Combinatorica
<< IGraphM

• Your question is either a duplicate of this question, or you need to add more information as to why it is different. – Jason B. Jan 21 at 22:48
• @JasonB. Thanks, I found that answer earlier. First, I don't need the chromatic polynomial, I need actual vertex color assignments. But second, I cannot load the packages described in that answer. Maybe that's just my ignorance: Get::noopen: Cannot open IGraphM. – Joseph O'Rourke Jan 21 at 22:55
• @JasonB. Oh, I see, needed to download the package. Got it! I will delete this question after a while. – Joseph O'Rourke Jan 21 at 23:02
• – kglr Jan 21 at 23:05
• External packages, written by the community, are very powerful, but definitely not as easy to find as they should be. If you find IGraphM to be useful, give kudos to Szabolcs. – Jason B. Jan 21 at 23:15

IGraph/M has extensive and very fast graph colouring functionality (both exact and approximate), but it is not API-compatible with the now deprecated Combinatorica. In other words, loading <<IGraphM  is not going to make old Combinatorica code work without modifications. The modifications are worth it though as IGraph/M is much, much faster, and works with Mathematica's Graph data structure directly.

You will find many graph colouring examples in the IGraph/M documentation.

A small example:

Nest[IGMycielskian, CycleGraph[4], 2] // (* Mycielski construction increase the chromatic number *)
Graph[#, VertexSize -> Large, GraphStyle -> "BasicBlack"] & // (* styling: large vertices, black edges *)
IGVertexMap[ColorData[97], VertexStyle -> IGMinimumVertexColoring] (* style graph based on vertex colouring *)


The available functions are

• IGVertexColoring, IGEdgeColoring for fast heuristic colouring (not exact minimum).
• IGKVertexColoring, IGKEdgeColoring finds a colouring with no more than $$k$$ colours
• IGMinimumVertexColoring, IGMinimumEdgeColoring find a minimum colouring, and have performance that is competitive with the best you might find elsewhere.
• IGChromaticNumber, IGChromaticIndex just compute the minimum number of required colours.
• Thanks! I am already using it. – Joseph O'Rourke Jan 22 at 12:16
• @JosephO'Rourke Feedback is always welcome (feel free to email). – Szabolcs Jan 22 at 12:21