Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I'm looking to compute minimum vertex colorations (s.t. no two vertices of the same color share an edge: http://en.wikipedia.org/wiki/Graph_coloring) for graphs in Mathematica v9 with potentially up to a few hundred vertices. I noticed that there are some old functions for this in the Combinatorica package (MinimumVertexColoring and VertexColoring), however these seem to no longer work with Mathematica v9 graph data structures. Unfortunately, I couldn't find anything newer in the function directory.

How does one find a graph coloring in Mathematica v9, or at least the chromatic number of the graph? Is there anything that will guarantee a minimal coloring conditioned on a result being returned?

Sage has the following functionalities: http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_coloring.html, but I can't seem to find anything in Mathematica v9 for this.

Update - Let's take belisarius' suggestion to use ToCombinatoricaGraph (and Szabolcs code from Generating a graph where vertices correspond to points in an integer lattice and edges connect points less than a threshold distance apart, which doesn't clash with Combinatorica package definitions):

Needs["Combinatorica`"]
Needs["GraphUtilities`"]

pts = Tuples[Range[10], 2];
threshold = 2;

distances = With[{tr = N@Transpose[pts]}, Function[point, Sqrt[Total[(point - tr)^2]]] /@ pts];
G = SimpleGraph[AdjacencyGraph@UnitStep[threshold - distances], VertexCoordinates -> pts]

MinimumVertexColoring[ToCombinatoricaGraph[G]]

The output (for threshold = 2) is:

{1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3}

So this seems to work. I suppose the obvious questions would be:

Is it known what algorithm MinimumVertexColoring is actually using? The help directory says that it returns a minimum vertex coloring, but is it actually guaranteed to be minimal? In other words, what algorithm is being employed? (Partial answer: the algorithm is based on [Mehrotra, A. and Trick, M. A. "A Column Generation Approach for Graph Coloring." INFORMS J. on Computing 8, 344-354, 1996.] http://mathworld.wolfram.com/ChromaticNumber.html. I need to read the paper to determine if there are any caveats to obtaining an exact minimum coloring.

Also, can we place markers on the vertices in the Mathematica v9 graph structure indicating their color? It's not clear to me if ToCombinatoricaGraph is preserving vertex orderings when reporting a coloring?

share|improve this question
    
Check ToCombinatoricaGraph[] ... a tunnel between two universes –  belisarius Nov 8 '13 at 14:48
    
@belisarius See my update! –  user10456 Nov 8 '13 at 15:00
    
The coloring algorithms are documented here amazon.com/…, section 7-4. Sorry I don't know any free source –  belisarius Nov 8 '13 at 15:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.