Minimal Colouring of Graph Vertices

Question

Is there a way to colour graph vertices minimally in new Mathematica? I tried loading MinimalVertexColoring with the old Combinatorica package but it doesn't work and it seems to conflict with the function I'm using

gr = Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9}, {1 <-> 2, 1 <-> 3, 1 <-> 7, 
   1 <-> 9, 2 <-> 3, 2 <-> 5, 2 <-> 6, 2 <-> 7, 3 <-> 4, 3 <-> 5, 
   3 <-> 9, 4 <-> 5, 4 <-> 6, 4 <-> 8, 4 <-> 9, 5 <-> 6, 6 <-> 7, 
   6 <-> 8, 7 <-> 8, 7 <-> 9, 8 <-> 9}, 
  VertexCoordinates -> {{0, 2}, {1, 1}, {-1, 1}, {-1, -1}, {0, 
     0}, {1, -1}, {8, 4}, {0, -2}, {-8, 4}}, VertexLabels -> "Name"]   

VertexDegree[gr]

FindHamiltonianCycle[gr, All]

Answer 1

IGraph/M has excellent graph colouring functionality, and I now recommend it over Combinatorica.

<< IGraphM`

Graph[gr, VertexSize -> Large] //
 IGVertexMap[ColorData[105], VertexStyle -> IGMinimumVertexColoring]

---

There are two problems:

1. Combinatorica is an obsolete package and many of the function/symbol names conflict with new, builtin ones. You'll need to refer to these symbols with their fully qualified name, e.g. System`Graph and Combinatorica`Graph. Whenever a symbol name is shown in red, you'll need to prepend a context to indicate whether you're referring to a symbol from Combinatorica of the System` context.

2. Combinatorica has been around much longer than the builtin graph datatype and has its own distinct graph representation. You'll need to convert the graph to this format using ToCombinatoricaGraph from the GraphUtilities` package.

 

<< Combinatorica`
<< GraphUtilities`

gr = System`Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9}, {1 <-> 2, 1 <-> 3, 
   1 <-> 7, 1 <-> 9, 2 <-> 3, 2 <-> 5, 2 <-> 6, 2 <-> 7, 3 <-> 4, 
   3 <-> 5, 3 <-> 9, 4 <-> 5, 4 <-> 6, 4 <-> 8, 4 <-> 9, 5 <-> 6, 
   6 <-> 7, 6 <-> 8, 7 <-> 8, 7 <-> 9, 8 <-> 9}, 
  VertexCoordinates -> {{0, 2}, {1, 1}, {-1, 1}, {-1, -1}, {0, 
     0}, {1, -1}, {8, 4}, {0, -2}, {-8, 4}}, VertexLabels -> "Name", 
  VertexSize -> Large]

mvc = MinimumVertexColoring@ToCombinatoricaGraph[gr]

SetProperty[gr, 
 System`VertexStyle -> 
  Thread[System`VertexList[gr] -> (ColorData[97] /@ mvc)]]

---

Note: This trick is unfortunately not useful here because GraphUtilities`ToCombinatoricaGraph evaluates Needs["Combinatorica`"] each time it's evaluated, re-adding Combinatorica` to the context path. I have suggested fixing this to WRI on multiple accounts, but so far they haven't done it.