2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you need to use Combinatorica? If not EdgeStyle should be your friend :) $\endgroup$ – Öskå Apr 19 '14 at 10:30
  • $\begingroup$ @Ö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 :-) $\endgroup$ – Juho Apr 19 '14 at 10:33
  • $\begingroup$ Please define what you need to do on a working example. Combinatorica is much trickier to use than the rest :) $\endgroup$ – Öskå Apr 19 '14 at 10:35
  • $\begingroup$ @Öskå Thanks for the suggestion, done! $\endgroup$ – Juho Apr 19 '14 at 11:01
1
$\begingroup$

With IGraph/M, you can do the following:

CompleteGraph[4, EdgeStyle -> AbsoluteThickness[4]] // 
 IGEdgeMap[ColorData[68], EdgeStyle -> IGMinimumEdgeColoring]

enter image description here

| improve this answer | |
$\endgroup$
2
$\begingroup$
<< 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

| improve this answer | |
$\endgroup$

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.