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`
Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.Sign up to join this community
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, 2] // (* Mycielski construction increase the chromatic number *) Graph[#, VertexSize -> Large, GraphStyle -> "BasicBlack"] & // (* styling: large vertices, black edges *) IGVertexMap[ColorData, VertexStyle -> IGMinimumVertexColoring] (* style graph based on vertex colouring *)
The available functions are
IGEdgeColoringfor fast heuristic colouring (not exact minimum).
IGKEdgeColoringfinds a colouring with no more than $k$ colours
IGMinimumEdgeColoringfind a minimum colouring, and have performance that is competitive with the best you might find elsewhere.
IGChromaticIndexjust compute the minimum number of required colours.