# Minimal Colouring of Graph Vertices

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]


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

<< IGraphM

Graph[gr, VertexSize -> Large] //
IGVertexMap[ColorData, 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. SystemGraph and CombinatoricaGraph. 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 = SystemGraph[{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,
SystemVertexStyle -> Note: This trick is unfortunately not useful here because GraphUtilitiesToCombinatoricaGraph 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.