3
$\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$
4
  • $\begingroup$ Do you need to use Combinatorica? If not EdgeStyle should be your friend :) $\endgroup$
    – Öskå
    Commented Apr 19, 2014 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
    Commented Apr 19, 2014 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å
    Commented Apr 19, 2014 at 10:35
  • $\begingroup$ @Öskå Thanks for the suggestion, done! $\endgroup$
    – Juho
    Commented Apr 19, 2014 at 11:01

2 Answers 2

2
$\begingroup$

With IGraph/M, you can do the following:

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

enter image description here

$\endgroup$
3
$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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