Edge Coloring

Author

Eric W. Weisstein
January 16, 2018

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/EdgeColoring.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/EdgeColoring.html.

©2018 Wolfram Research, Inc. except for portions noted otherwise

Figure

Combinatorica

edgeColors[g_Graph]:=Module[
{
l=EdgeColoring[g],
n,
colors={Red,Green,Blue,Purple,Orange,Yellow,LightBlue,Black}
},
n=Max[l];
RGBColor@@@Take[colors,n][[l]]
]

gr[g_Graph]:=Graphics[showGraph[g,
EdgeColors->edgeColors[g],
PlotStyles->{AbsolutePointSize[7],AbsoluteThickness[2]}],
PlotRange->All]

Show[GraphicsArray[{gr/@{Wheel[8],UtilityGraph,PetersenGraph,FruchtGraph}}]]

V7 Graph

Table[Show[Graphics[{Hue[i /10],Disk[{0,0},1]}],ImageSize->Tiny],{i,0,9}]

ColoredEdges[g_,inds_]:=Module[{colfn,el=EdgeList[g],ecn=Max[inds],defcols={Red,Green,Blue,Yellow}},If[Length[inds]=!=Length[el],Return[$Failed]];
If[ecn≤Length[defcols],colfn[c_]:=defcols[[c]],(*Else*)colfn[c_]:=Hue[(c-1.)/ecn]];
SetProperty[g,System`EdgeStyle->(MapIndexed[el[[#2[[1]]]]->Directive[Thick,colfn[#]]&,inds])]]

ColoredEdges[GraphData[{"Wheel",8}],GraphData[{"Wheel",8},"MinimumEdgeColoring"]]

Algorithm

?FindMinimumEdgeColoring

?EdgeColoringQ

GraphData[{"Circulant",{18,{2}}},"ConnectedComponentGraphNames"]

GraphData["C9","EdgeChromaticNumber"]

Grid[With[{g={"Circulant",{18,{2}}}},{#,coloring=FindMinimumEdgeColoring[GraphData[g],GraphData[g,"EdgeChromaticNumber"],Method->#],If[coloring===$Failed,coloring,EdgeColoringQ[GraphData[g],coloring]]}]&/@{"Brelaz","Blossom","FindIndependentEdgeSet","VizingKempe"},Dividers->All,Alignment->Left]

Blossom can  give wrong answers

ColoredEdges[GraphData[{"Circulant",{18,{2}}}],{1,1,2,2,1,1,2,2,1,1,2,2,1,1,2,3,2,3}]

Inconsistency between edge chromatic number and coloring

<<MathWorld`Graphs`

EdgeChromaticNumber[GraphData[{"Antiprism",21}],Debug->True]

FindIndependentEdgeSet

FindEdgeColoring[GraphData[{"Antiprism",21}],Method->"FindIndependentEdgeSet",Debug->True]

ILP

col=FindEdgeColoring[GraphData[{"Antiprism",21}],Method->{"ILP",4},Debug->True]

EdgeColoringQ[GraphData@{"Antiprism",21},col]

VizingClass1

col=FindEdgeColoring[GraphData[{"Antiprism",21}],Method->"VizingClass1",Debug->True]

EdgeColoringQ[GraphData@{"Antiprism",21},col]