Fractional Coloring

Author

Eric W. Weisstein
December 7, 2015

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

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

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

Algorithms

Monitor[DeleteCases[Function[g,{gr=g,FractionalChromaticNumber[FindFractionalColoring[GraphData[g],Method->#,"Preprocess"->False]]&/@{"Static","Trick"}}]/@GraphData[;;10],{_,{x_,x_}}],gr]//Timing

Monitor[DeleteCases[Function[g,{gr=g,FractionalChromaticNumber[FindFractionalColoring[GraphData[g],Method->#]]&/@{"Static","Trick"}}]/@GraphData[;;10],{_,{x_,x_}}],gr]//Timing

Wagon

<<Wagon`GraphsWagon`

FractionalChromaticNumberAndColoring[GraphData[{"Antiprism",5}],TraceQ->True]

FractionalChromaticNumberAndColoring[GraphData[{"Cyclotomic",67}],TraceQ->True]

FractionalChromaticNumberAndColoring[GraphData[{"Antiprism",5}],TraceQ->True]

Quit

My version

FindFractionalColoring[GraphData[{"Cyclotomic",67}],Method->"Trick",Debug->True]//Timing

FractionalColoringIndependentSetForm@{{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{2,1}},{{1,1}},{{3,1}}}

GraphData[{"Helm",14},"LabeledImage"]

FindFractionalColoring[GraphData[{"Helm",14}],Debug->True,Method->"Trick"]//Timing

FindFractionalColoring[GraphData[{"Helm",13}],Debug->True,Method->"Static"]//Timing

Quit

FindFractionalColoring[GraphData[{"Antiprism",18}],Debug->True,Method->"Trick"]

FindFractionalColoring[GraphData[{"ZeroTwoNonbipartite",{7,38}}],Debug->True,Method->"Trick"]

FindFractionalColoring[GraphData[{"ZeroTwoNonbipartite",{7,38}}],Debug->True,Method->"Trick"]

Test

?FindFractionalColoring

Bipartite

FindFractionalColoring[GraphData["ForkGraph"]]

FractionalColoringVertexForm[%]

FindFractionalColoring[GraphData["ForkGraph"],Debug->True]

FindFractionalColoring[GraphData["ForkGraph"],Debug->True,"Preprocess"->False]

C5

Vertex form

(col=FindFractionalColoring[GraphData["C5"]])

FractionalColoringVertexForm[FindFractionalColoring[GraphData["C5"]]]

Vertex 1 gets color 4 with weight 1/2 and color 5 with weight 1/2
Vertex 2 gets color 2 with weight 1/2 and color 3 with weight 1/2
Vertex 3 gets color 1 with weight 1/2 and color 5 with weight 1/2
Vertex 4 gets color 3 with weight 1/2 and color 4 with weight 1/2
Vertex 5 gets color 1 with weight 1/2 and color 2 with weight 1/2

Vertex count

Length[col]

Total/@col[[All,All,2]]

Independent set form

FractionalColoringIndpendentSetForm[col]

(col=FindFractionalColoring[GraphData["C5"]])

Vertices 3 and 5 get color 1 with weight 1/2
Vertices 2 and 5 get color 2 with weight 1/2
Vertices 2 and 4 get color 3 with weight 1/2
Vertices 1 and 4 get color 4 with weight 1/2
Vertices 1 and 3 get color 5 with weight 1/2

Color count

Length[%]

FractionalChromaticNumber[col]

DodecahedralGraph

(col=FindFractionalColoring[GraphData["DodecahedralGraph"]])//Timing

FractionalColoringVertexForm[%]

Vertex count

Length[col]

Total/@col[[All,All,2]]

FractionalColoringIndpendentSetForm[col]

FindFractionalColoring[GraphData["DodecahedralGraph"]]

Color count

Length[%]

FractionalChromaticNumber[col]

TilleyGraph

(col=FindFractionalColoring[GraphData["TilleyGraph"]])//Timing

Vertex count

Length[col]

FractionalColoringIndpendentSetForm[col]

FindFractionalColoring[GraphData["TilleyGraph"]]

Color count

Length[%]

FractionalChromaticNumber[col]

N[%]

TwoPentagons

(col=FindFractionalColoring[GraphData["TwoPentagons"]])//Timing

Vertex count

Length[col]

Total/@col[[All,All,2]]

FractionalColoringIndpendentSetForm[col]

Color count

Length[%]

FractionalChromaticNumber[col]

N[%]

ThreePentagons

(col=FindFractionalColoring[GraphData["ThreePentagons"]])//Timing

Vertex count

Length[col]

Total/@col[[All,All,2]]

FractionalColoringIndpendentSetForm[col]

Color count

Length[%]

FractionalChromaticNumber[col]

N[%]

FourPentagons

(col=FindFractionalColoring[GraphData["FourPentagons"]])//Timing

Vertex count

Length[col]

Total/@col[[All,All,2]]

FractionalColoringIndpendentSetForm[col]

Color count

Length[%]

FractionalChromaticNumber[col]

N[%]

Visualize

ColoredDisk[cols_, fracs_]:=Module[{acc=Accumulate[Prepend[fracs,0]]},
acc=Partition[2π acc,2,1];Graphics[
Table[{cols[[i]], EdgeForm[{Black, Thickness[.04]}],Disk[{0,0},2,acc[[i]] ]}, {i, Length[cols]}]]
]

GraphPlotFractional[g_System`Graph,opts___?OptionQ] := GraphPlotFractional[g,FractionalChromaticNumberAndColoring[g],opts]

GraphPlotFractional[g_System`Graph, frac_List, opts___?OptionQ] := Module[{},
fracValuesOfColors= Last/@ Union[Flatten[frac[[2]],1]];
realcols=Join[{Red, Green,Yellow, Blue, Cyan, Magenta, Brown, Orange, Purple, Black, Pink, Gray},ColorData["Legacy"]/@ Range[100]];
cols=Union[First/@ Flatten[frac[[2]],1]];
SetProperty[g,{VertexSize->Large,opts,VertexShape->MapIndexed[#2[[1]]->ColoredDisk[realcols[[First/@ frac[[2,#2[[1]]]]]],fracValuesOfColors[[First/@ frac[[2,#2[[1]]]]]]]&, VertexList[g]]}]
]

GraphPlotColoring[g_System`Graph,opts___?OptionQ]:=GraphPlotColoring[g,MinimumVertexColoring[FromUnorderedPairs[List@@@EdgeList[g]]],opts]

GraphPlotColoring[g_System`Graph,colors_List,opts___?OptionQ]:=Module[
{
colorlist=Join[{Red, Green,Yellow, Blue, Cyan, Magenta, Brown, Orange, Purple, Black, Pink, Gray},ColorData["Legacy"]/@ Range[100]]
},
SetProperty[g,{VertexSize->.3,opts,System`VertexStyle->MapIndexed[#2[[1]]->#1&,colors/.Thread[Range[Max@colors]->Take[colorlist,Max@colors]]]}]
]

ColoredDisk[col_]:=Module[{n=Length[col]},
Graphics[{
MapIndexed[{#1,Disk[{0,0},1,π/2+{#2[[1]]-1,#2[[1]]}2π/n]}&,col],
Circle[{0,0},1],Switch[n,
1,{},
_?EvenQ,Line[Table[{Through[{Sin,Cos}[2π i/n]],Through[{Sin,Cos}[π+2π i/n]]},{i,n/2}]],
_?OddQ,Line[Table[{{0,0},Through[{Sin,Cos}[2π i/n]]},{i,0,n-1}]]
]
}
]
]

With[{n=2},Line[Table[{Through[{Cos,Sin}[2π i/n]],Through[{Cos,Sin}[π+2π i/n]]},{i,n/2}]]]

ColoredDisk/@NestList[Most,{Red,Yellow,Green,Blue},3]

colors=MinimumVertexColoring[Graph["DodecahedralGraph"]]

colorlist={Red,Yellow,Green,Blue,Purple};

FractionalChromaticNumberAndColoring[GraphData["DodecahedralGraph"]]

GraphData[{"Septic",{10,4}}]

FractionalChromaticNumberAndColoring[GraphData[{"Septic",{10,4}}]]

l0={{{1,9},(1/2)},{{2,8},(1/2)},{{3,7},(1/2)},{{4,5,6},1},{{1,10},(1/2)},{{10,2},(1/2)},{{3,9},(1/2)},{{7,8},(1/2)}}[[All,1]]

l1=Flatten[Partition[#,2,1]&/@l0,1]

l2=Sort/@(Position[l1,#][[All,1]]&/@Range[10])

colorlist={Red,Orange,Yellow,Green,Blue,Purple,Brown,Black}

SetProperty[GraphData[{"Septic",{10,4}}],{VertexSize->Large,VertexShape->MapIndexed[#2[[1]]->ColoredDisk[#1/.Thread[Range[10]->colorlist]]&,l2]}]

fc=FractionalChromaticNumberAndColoring[g=GraphData[{"Sextic",{10,2}}]]

l0=fc[[2,All,1]]

l1=Flatten[Partition[#,2,1]&/@l0,1]

l2=Sort/@(Position[l1,#][[All,1]]&/@Range[10])

colorlist={Red,Orange,Yellow,Green,Blue,Purple,Brown,Black}

SetProperty[g,{VertexSize->Large,VertexShape->MapIndexed[#2[[1]]->ColoredDisk[#1/.Thread[Range[VertexCount[g]]->colorlist]]&,l2]}]

fc=FractionalChromaticNumberAndColoring[g=GraphData[{"Quintic",{10,57}}]]

Total@fc[[2,All,2]]

l0=fc[[2,All,1]]

l1=Flatten[Partition[#,2,1]&/@l0,1]

l2=Sort/@(Position[l1,#][[All,1]]&/@Range[VertexCount[g]])

Length[colorlist={Red,Orange,LightOrange,Yellow,LightGreen,Green,LightBlue,Cyan,Blue,Pink,Magenta,Purple,LightBrown,Brown,Black}]

SetProperty[g,{VertexSize->Large,VertexShape->MapIndexed[#2[[1]]->ColoredDisk[#1/.Thread[Range[15]->Take[colorlist,15]]]&,l2]}]

FractionalChromaticNumberAndColoring[GraphData[{"JohnsonSkeleton",46}]]

GraphPlotFractional[{"JohnsonSkeleton",46}]

From Stan

GraphPlotFractional[GraphData["ErreraGraph"],VertexSize->.7]

GraphPlotFractional[GraphData@{"Quintic",{10,57}}]

GraphPlotFractional[GraphData@{"GeneralizedPetersen",{14,6}},VertexSize->.7]

Figures

DodecahedralGraph

g1=GraphPlotColoring[GraphData["DodecahedralGraph"],VertexSize->.5]

g2=GraphPlotFractional[GraphData["DodecahedralGraph"],VertexSize->.7]

GraphicsRow[{g1,g2},ImageSize->500]

Pentagons

Max[Flatten[FractionalChromaticNumberAndColoring[GraphData[#]][[2]],1][[All,1]]]&/@{{"Cycle",5},"TwoPentagons","ThreePentagons"}

c1=GraphPlotColoring[GraphData[{"Cycle",5}]]

FractionalChromaticNumberAndColoring[GraphData[{"Cycle",5}]]

f1=GraphPlotFractional[GraphData[{"Cycle",5}]]

f2=GraphPlotFractional[GraphData["TwoPentagons"],VertexSize->.2]

f3=GraphPlotFractional[GraphData["ThreePentagons"],VertexSize->.2]

FractionalChromaticNumberAndColoring[GraphData["TwoPentagons"]]

g12=GraphPlotFractional[GraphData["TwoPentagons"],VertexSize->.7]

p3=FractionalChromaticNumberAndColoring[GraphData["ThreePentagons"]]

GraphData["ThreePentagons","LabeledImage"]

g2=GraphPlotFractional[GraphData["ThreePentagons"],VertexSize->.7]

g2=GraphPlotFractional[GraphData["C5"],{5/2,Take[p3[[2]],5][[{1,2,4,5,3}]]}]

Through[{ChromaticNumberTrick,FractionalChromaticNumber}[GraphData[#]]]&/@{"SquareGraph","TwoSquares","ThreeSquares","FourSquares",{"Cycle",5},"TwoPentagons","ThreePentagons"}

GraphicsRow[{c1,f1,g2},ImageSize->500]

Bug

bug(304854)

Stan's ILP

$Version

$TopDirectory

ISByLPRational[S_]:=Module[{n=Length[S],v,obj,con0,con1,con1Left,x,verts},v=x/@Range[n];
obj=Total[v];
verts=Union@@S;
con0=Thread[0≤v];
con1Left=Table[Total[x/@Select[Range[n],MemberQ[S[[#]],j]&]],{j,verts}];
con1=Thread[con1Left≥1];
Minimize[{obj,Flatten[{con0,con1}]},v]]

FractionalColoring[g_System`Graph]:=Module[{S,solx,i,inds,posns,nv,wts},nv=VertexCount[g];
solx=ISByLPRational[S=FindIndependentVertexSet[g,Infinity,All]];
inds=Cases[solx[[2]],HoldPattern[r_[z_]->p_]:>{S[[z]],p}];
inds=DeleteCases[inds,{_,0}];
wts=inds[[All,-1]];
Table[Transpose@{posns=Position[inds,i][[All,1]],wts[[posns]]},{i,nv}]]

(col=FractionalColoring[GraphData["SchlaefliDoubleSixesGraph"]])//Timing

FractionalChromaticNumber[fraccol_List]:=Total[Union[Flatten[fraccol,1]][[All,-1]]]

FractionalChromaticNumber[col]

N[%,10]

Trick

GraphData["SchlaefliDoubleSixesGraph","IndependentVertexSetCount"]

GraphData["SchlaefliDoubleSixesGraph","MaximalIndependentVertexSetCount"]