4
$\begingroup$

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`
Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Your question is either a duplicate of this question, or you need to add more information as to why it is different. $\endgroup$ – Jason B. Jan 21 at 22:48
  • $\begingroup$ @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`. $\endgroup$ – Joseph O'Rourke Jan 21 at 22:55
  • 1
    $\begingroup$ @JasonB. Oh, I see, needed to download the package. Got it! I will delete this question after a while. $\endgroup$ – Joseph O'Rourke Jan 21 at 23:02
  • 2
    $\begingroup$ see also: How to color nodes in a adjacency graph with different colors? $\endgroup$ – kglr Jan 21 at 23:05
  • 4
    $\begingroup$ 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. $\endgroup$ – Jason B. Jan 21 at 23:15
3
$\begingroup$

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 *)

enter image description here

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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! I am already using it. $\endgroup$ – Joseph O'Rourke Jan 22 at 12:16
  • $\begingroup$ @JosephO'Rourke Feedback is always welcome (feel free to email). $\endgroup$ – Szabolcs Jan 22 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.