Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Combinatorica has a heuristic edge-coloring function EdgeColoring. When I execute it on a graph, the result is a list of integers. My guess is that an integer $i$ at position $j$ in the list corresponds to coloring the edge $e$ at position $j$ with the color $i$.

The Combinatorica documentation is helplessly scarce, and it's hard for a beginner to understand how to visualize the colored graph. Am I supposed to use ShowGraph, or Highlight, or something else? For example, consider the following.

<< Combinatorica`
g = CompleteGraph[4];
c = EdgeColoring[g];

The output is now {1, 2, 3, 3, 2, 1}. How do I print out the graph with the colors on the edges showing?

share|improve this question
Do you need to use Combinatorica? If not EdgeStyle should be your friend :) – Öskå Apr 19 '14 at 10:30
@Öskå I think I do -- at least for finding the edge-coloring. That is, as far as I know, there is no heuristic nor exact edge-coloring algorithm in Mathematica not depending on Combinatorica. I suppose you could always convert a Combinatorica graph to a built-in graph, but the visualization problem still persists :-) – Juho Apr 19 '14 at 10:33
Please define what you need to do on a working example. Combinatorica is much trickier to use than the rest :) – Öskå Apr 19 '14 at 10:35
@Öskå Thanks for the suggestion, done! – Juho Apr 19 '14 at 11:01
up vote 1 down vote accepted
<< Combinatorica`
g = CompleteGraph[4];
c = EdgeColoring[g];
colors = ColorData[1, "ColorList"] (* say *);
ShowGraph[g, VertexLabel -> True, EdgeColor -> colors[[c]]]

enter image description here

For graphs in GraphData[], you can use the "MinimumEdgeColoring" property:

g2 = GraphData[{"Complete", 4}];
c2 = GraphData[{"Complete", 4}, "MinimumEdgeColoring"];
edges = EdgeList[g2];
Graph[Style @@@ Thread[{edges, Thick, colors[[c2]]}], 
       VertexLabels -> "Name", ImagePadding -> 10]

enter image description here

share|improve this answer

Your Answer


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

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