6
$\begingroup$

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]
$\endgroup$
11
$\begingroup$

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

<< IGraphM`

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

enter image description here


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

Mathematica graphics


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.

$\endgroup$
  • $\begingroup$ For some reason it's not colouring the graph directly as in your answer but gives it as an ordered list of numbers from 1-4, which is still ok. Do you know of a way to randomise the colouring? $\endgroup$ – A. Napster Nov 30 '14 at 10:47

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.