Fractional Chromatic Number

Author

Eric W. Weisstein
January 1, 2024

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

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

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

Table

GraphDataCountTable["FractionalChromaticNumber"]

Missing

DateString[]

Grid[missing=Cases[Sort[GraphData[#,{"V","FractionalChromaticNumber","#"}]&/@GraphData[All]],{v_,_Missing,g_}:>{v,g}],Alignment->{{Decimal,Left}},Dividers->All]

Length[missing]

Export[file="/Users/eww/Documents/Mathematica/Paclets/GraphData/Data/ForPratt/FractionalChromaticNumber.tsv",{GraphNameToPrattName[#2],GraphData[#2,"V"],GraphData[#2,"M"]}&@@@missing]

(Subscript[χ, f]) == χ

Connected

A243252

Table[Total[Boole[ChromaticNumber[#]==FractionalChromaticNumber[FindFractionalColoring[#]]&/@ConnectedGraphs[n]]],{n,8}]//Timing

Table[Length@Select[GraphData["Connected",n],Equal@@GraphData[#,{"FractionalChromaticNumber","ChromaticNumber"}]&],{n,7}]

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[ConnectedIndices[[n]]]]&/@{"ChromaticNumber","FractionalChromaticNumber"}]]],{n,10}]//Timing

Disconnected

A287008

Table[Length@Select[GraphData["Disconnected",n],Equal@@GraphData[#,{"FractionalChromaticNumber","ChromaticNumber"}]&],{n,7}]

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[DisconnectedIndices[[n]]]]&/@{"ChromaticNumber","FractionalChromaticNumber"}]]],{n,10}]//Timing

All

A287007

Table[Length@Select[GraphData[n],Equal@@GraphData[#,{"FractionalChromaticNumber","ChromaticNumber"}]&],{n,7}]

Table[Total[Boole[Equal@@@Transpose[Get[FileNameJoin[{$GraphDataDirectory,"Nodes",#,#<>"_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]]&/@{"ChromaticNumber","FractionalChromaticNumber"}]]],{n,10}]//Timing

GraphData

Table[Select[GraphData[n],Equal@@GraphData[#,{"FractionalChromaticNumber","ChromaticNumber"}]&],{n,5}]

Length[s1=Select[Graphs[8],ChromaticNumber[#]==FractionalChromaticNumber[FindFractionalColoring[#]]&]]//Timing

Length[s2=Select[Graphs[8],ChromaticNumber[#]==CliqueNumber[#]&]]//Timing

Complement[s1,s2]

ToEntity/@%

CanonicalName[%]

GraphData[#,{"CliqueNumber","ChromaticNumber","FractionalChromaticNumber"}]&/@%32

Complement[s2,s1]

(Subscript[χ, f]) == χ but not vertex-transitive

data=GraphData[#,{"#","ChromaticNumber","FractionalChromaticNumber"}]&/@Complement[GraphData["χ","Defined"],GraphData["VertexTransitive"]];

SortBy[Cases[data,{g_,x_,x_}:>g],GraphData[#,"V"]&]

Archimedean Dual

Grid[data=GraphData[#,{"#","ChromaticNumber","FractionalChromaticNumber"}]&/@GraphData["ArchimedeanDual"],Dividers->All,Alignment->Left]

These differ:

DeleteCases[data,{_,x_,x_}]

(Subscript[χ, f]) and χ are integers but (Subscript[χ, f]) ≠ χ

TextGrid[Sort@DeleteCases[
Cases[GraphData[#,{"ChromaticNumber","FractionalChromaticNumber","#"}]&/@GraphData[All],
{_Integer,_Integer,_}],
{x_,x_,_}],Dividers->All,Alignment->{{{Decimal},Left}}]

Example from Scheinerman and Ullman, Fig 4.1, p. 70

(newg=AddEdges[AddVertices[DeleteEdges[ChangeVertices[g=Graph[{"Prism",{5,3}}],RotationMatrix[-.15].#&/@Vertices[g]],{{4,9},{9,14},{3,8},{8,13},{2,7},{7,12},{1,6},{6,11},{5,10},{10,15},{5,1},{6,10}}],{{2.5,-2},{3,0},{-1,3},{-3,0},{-2.5,-2.0}}],{{18,13},{18,8},{18,3},{2,17},{7,17},{12,17},{6,5},{10,1},{11,16},{6,16},{1,16},{20,15},{20,10},{20,5},{19,14},{19,9},{19,4}}])//ShowLabeledGraph

newg//InputForm

newg=Graph[{{{1, 2}}, {{2, 3}}, {{3, 4}}, {{4, 5}}, {{6, 7}}, {{7, 8}}, {{8, 9}}, {{9, 10}}, {{11, 12}}, {{11, 15}}, 
  {{12, 13}}, {{13, 14}}, {{14, 15}}, {{13, 18}}, {{8, 18}}, {{3, 18}}, {{2, 17}}, {{7, 17}}, {{12, 17}}, {{5, 6}}, 
  {{1, 10}}, {{11, 16}}, {{6, 16}}, {{1, 16}}, {{15, 20}}, {{10, 20}}, {{5, 20}}, {{14, 19}}, {{9, 19}}, {{4, 19}}}, 
 {{{0.5934083924419471, -0.8047139117596165}}, {{0.9488399425840277, 0.31575269334898626}}, 
  {{-0.0066034132741065454, 1.000218173666691}}, {{-0.9535934763349282, 0.3018931630419386}}, 
  {{-0.5820514454169401, -0.8131501182979997}}, {{1.1868167848838942, -1.609427823519233}}, 
  {{1.8976798851680554, 0.6315053866979725}}, {{-0.014345035758622726, 1.99959701438792}}, 
  {{-1.9060487434594469, 0.6046256590293397}}, {{-1.1641028908338802, -1.6263002365959993}}, 
  {{1.7802251773258415, -2.4141417352788492}}, {{2.846519827752083, 0.947258080046959}}, 
  {{-0.0209484490327293, 2.9998151880546113}}, {{-2.859642219794375, 0.9065188220712783}}, 
  {{-1.7461543362508203, -2.439450354893999}}, {{2.5, -2}}, {{3, 0}}, {{-1, 3}}, {{-3, 0}}, {{-2.5, -2.}}}];

RecognizeGraph[newg]

GraphData[{"Flower",5},{"ChromaticNumber","FractionalChromaticNumber"}]

GraphData[{"Flower",5},"Graph","All"]

FractionalChromaticNumber[GraphData[{"Flower",5}],Debug->True]//Timing

#>=1

diff=Select[GraphData[All],Head[fc=GraphData[#,"FractionalChromaticNumber"]]=!=Missing&&Head[c=GraphData[#,"ChromaticNumber"]]=!=Missing&&fc=!=c&&IntegerQ[fc]&];

Grid[GraphData[#,{"#","FractionalChromaticNumber","ChromaticNumber"}]&/@SortBy[diff,GraphData[#,"V"]&],Dividers->All,Alignment->{{Left,Decimal,Decimal},Automatic}]

#>1

diff=Select[GraphData[All],Head[fc=GraphData[#,"FractionalChromaticNumber"]]=!=Missing&&Head[c=GraphData[#,"ChromaticNumber"]]=!=Missing&&c-fc>1&&IntegerQ[fc]&];

Grid[GraphData[#,{"#","FractionalChromaticNumber","ChromaticNumber"}]&/@SortBy[diff,GraphData[#,"V"]&],Dividers->All,Alignment->{{Left,Decimal,Decimal},Automatic}]

GraphData[{"Kneser",{8,2}},"V"]

ChromaticNumberAndColoring[GraphData[{"Kneser",{8,2}}]]//Timing

ChromaticNumberByILP[Graph[{"Kneser",{8,2}}]]//Timing

GraphData[{"Kneser",{8,2}},"ChromaticNumber"]

FractionalChromaticNumberTrick[GraphData[{"Kneser",{8,2}}]]//Timing

GraphData[{"Kneser",{8,2}},"FractionalChromaticNumber"]

ConnectedGraphQ/@GraphData/@diff

DeleteCases[diff,{"Kneser",_}]

Gimbel, Kündgen, Li and Thomassen (2019) conjecture counterexamples

Chiu et al. 2021:

This disproves the conjecture of Gimbel, Kündgen, Li and Thomassen (2019) that every 4-chromatic planar graph has fractional chromatic number strictly greater than 3.

chi4chif3=Select[GraphData["Planar"],GraphData[#,"ChromaticNumber"]===4&&GraphData[#,"FractionalChromaticNumber"]<=3&]

GraphicsRow[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.02}],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[14,Black,Italic,FontFamily->"Times New Roman",Hyphenation->True]],PageWidth->160,TextAlignment->Center]]&/@chi4chif3,Dividers->All,ImageSize->500]

Checks

Static

Select[GraphData[;;10],FindFractionalChromaticNumberAndColoring[GraphData[#]][[1]]=!=GraphData[#,"FractionalChromaticNumber"]&]//Timing

Select[GraphData[;;4],FindFractionalChromaticNumberAndColoring[GraphData[#],Method->"Trick"][[1]]=!=GraphData[#,"FractionalChromaticNumber"]&]//Timing

Select[GraphData[;;5],FindFractionalChromaticNumberAndColoring[GraphData[#],Method->"Trick"][[1]]=!=GraphData[#,"FractionalChromaticNumber"]&]//Timing

Print[{#,FindFractionalChromaticNumberAndColoring[GraphData[#]][[1]]//Timing}]&/@{{9,31016},{"TriangularHoneycombObtuseKnight",5},{"TriangularHoneycombQueen",5},{"TriangularHoneycombObtuseKnight",6},{"TriangularHoneycombQueen",6},{"TriangularHoneycombAcuteKnight",7},{"TriangularHoneycombObtuseKnight",7},{"TriangularHoneycombQueen",7},{"TriangularHoneycombAcuteKnight",8},{"TriangularHoneycombObtuseKnight",8},{"TriangularHoneycombQueen",8}}

Print[{#,FindFractionalChromaticNumberAndColoring[GraphData[#],"OptimizationMethod"->Maximize][[1]]//Timing}]&/@{{9,31016},{"TriangularHoneycombObtuseKnight",5},{"TriangularHoneycombQueen",5},{"TriangularHoneycombObtuseKnight",6},{"TriangularHoneycombQueen",6},{"TriangularHoneycombAcuteKnight",7},{"TriangularHoneycombObtuseKnight",7},{"TriangularHoneycombQueen",7},{"TriangularHoneycombAcuteKnight",8},{"TriangularHoneycombObtuseKnight",8},{"TriangularHoneycombQueen",8}}

GraphData["WienerArayaGraph","IndependentVertexSetCount"]

GraphData["WienerArayaGraph","IndependentVertexSetCount"]

FindFractionalChromaticNumberAndColoring[GraphData["WienerArayaGraph"]]//Timing

General

def=SortBy[GraphData["FractionalChromaticNumber","Defined"],GraphData[#,"V"]&];

Position[def,{"JohnsonSkeleton",43}]

Monitor[If[(f1=FractionalChromaticNumberTrick[GraphData[g=#]])=!=(f2=GraphData[#,"FractionalChromaticNumber"]),Print[{#,f1,f2}]]&/@Drop[def,5330],g]

Checked through but not including {"Fullerene", {50,9}}

Bad ones

GraphData["GewirtzGraph","FractionalChromaticNumber"]

FractionalChromaticNumberTrick[GraphData["GewirtzGraph"]]//Timing

FractionalChromaticNumberTrick[GraphData["Foster054A"]]//Timing

FractionalChromaticNumberTrick[GraphData["Foster054A"]]//Timing

FractionalChromaticNumberTrick[GraphData["PerkelGraph"]]//Timing

non-VT

Select[GraphData["IndependenceNumber","Defined"],GraphData[#,"FractionalChromaticNumber"]<GraphData[#,"V"]/GraphData[#,"IndependenceNumber"]&]

VT

Select[Intersection[GraphData["VertexTransitive"],GraphData["IndependenceNumber","Defined"]],GraphData[#,"FractionalChromaticNumber"]=!=GraphData[#,"V"]/GraphData[#,"IndependenceNumber"]&]

Select[%,Head[GraphData[#,"FractionalChromaticNumber"]]=!=Missing&]

Compare LP and Trick

Length[gs=SortBy[GraphData["FractionalChromaticNumber","Defined"],GraphData[#,"V"]&]]

checked=3622;
skipped=49;
timeout=10;
skippedgs={};
Monitor[TimeConstrained[If[(cf1=FractionalChromaticNumber[GraphData[g=#]])=!=(cf2=FractionalChromaticNumberTrick[GraphData[g]]),Print[{g,cf1,cf2}]];checked++,timeout,AppendTo[skippedgs,g];skipped++]&/@Drop[gs,checked+skipped],{g,skipped,checked}]

1

Parametrized families

<<MathWorld`Graphs`

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"FractionalChromaticNumber"],{n,10}]

FindSequenceFunction[seq,n]

Antiprism

Entity["Graph",{"Antiprism",n}]["FractionalChromaticNumber"]//TraditionalForm

Inferred for n > 11:

seq=Table[GraphData[{"Antiprism",n},"FractionalChromaticNumber"],{n,3,25}]

Table[Piecewise[{{3, Mod[n, 3] == 0}, {(3*n)/(-1 + n), Mod[n, 3] == 1}, {(6*n)/(-1 + 2*n), Mod[n, 3] == 2}}, 0],{n,3,25}]==seq

Apollonian

seq=Table[GraphData[{"Apollonian",n},"FractionalChromaticNumber"],{n,6}]

Barbell

Inferred for n > 12:

seq=Table[GraphData[{"Barbell",n},"FractionalChromaticNumber"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"FractionalChromaticNumber"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"FractionalChromaticNumber"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"FractionalChromaticNumber"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"FractionalChromaticNumber"],{n,10}]

CocktailParty

Inferred for n > 13:

seq=Table[GraphData[{"CocktailParty",n},"FractionalChromaticNumber"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Complete",n},"FractionalChromaticNumber"],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["FractionalChromaticNumber"]

Block[{m,n},DeleteCases[{
#,
{m,n}=("CompleteBipartite"/.GraphData[#,"NotationRules"]);2,
GraphData[#,"FractionalChromaticNumber"]
}&/@GraphData["CompleteBipartite"],{_,x_,x_}]]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"FractionalChromaticNumber"],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["FractionalChromaticNumber"]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"FractionalChromaticNumber"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"FractionalChromaticNumber"],{n,2,10}]

Crown

seq=Table[GraphData[{"Crown",n},"FractionalChromaticNumber"],{n,3,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["FractionalChromaticNumber"]

Entity["Graph",{"CubeConnectedCycle",n}]["IndependenceNumber"]

Entity["Graph",{"CubeConnectedCycle",n}]["VertexCount"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"FractionalChromaticNumber"],{n,3,8}]

?FractionalChromaticNumber

Table[GraphData[{"CubeConnectedCycle",n},"VertexTransitive"],{n,3,8}]

Table[FractionalChromaticNumber[GraphData[{"CubeConnectedCycle",n}],Method -> NMaxValue],{n,3,3}]//Timing

Table[Piecewise[{{(2^(n-1)) n ,Mod[n,2]==0},{(2^(n-1))  (n-1),Mod[n,2]==1}}],{n,3,8}]

Table[Piecewise[{{2,Mod[n,2]==0},{((2n)/(n-1)),Mod[n,2]==1}}],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["FractionalChromaticNumber"]//TraditionalForm

seq=Table[GraphData[{"Cycle",n},"FractionalChromaticNumber"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Empty",n},"FractionalChromaticNumber"],{n,30}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"FractionalChromaticNumber"],{n,3,14}]

Do[With[{debug=False,gn={"DiagonalIntersection",n}},
Print[{
If[debug,Print[{gn,GraphData[gn,"FractionalChromaticNumber"],N@GraphData[gn,"FractionalChromaticNumber"]}]];
gn,
TimeConstrained[
FindFractionalColoring[
GraphData[gn],
Method->"Dynamic",
Debug->debug,
MaxSteps->10^6
],Infinity]//Timing}]],{n,3,14}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"FractionalChromaticNumber"],{n,15}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"FractionalChromaticNumber"],{n,2,10}]

Table[GraphData[{"FoldedCube",n},"VertexTransitive"],{n,2,10}]

Table[GraphData[{"FoldedCube",n},"IndependenceNumber"],{n,2,10}]

Table[(2^(n-2))+((((-1))^n)-1)Binomial[n-1,(n-1)/2]/4,{n,2,10}]

Table[GraphData[{"FoldedCube",n},"VertexCount"],{n,2,10}]

FindSequenceFunction[%382,n-1]//Factor

Simplify[((2^(-1+n))/((2^(n-2))+((((-1))^n)-1)Binomial[n-1,(n-1)/2]/4)),Mod[n,2]==0]

FullSimplify[((2^(-1+n))/((2^(n-2))+((((-1))^n)-1)Binomial[n-1,(n-1)/2]/4)),Mod[n,2]==1]

Table[Piecewise[{{2,Mod[n,2]==0},{((2^(1+n))/((2^n)-2 Binomial[-1+n,(1/2) (-1+n)])),Mod[n,2]==1}}],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"FractionalChromaticNumber"],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["FractionalChromaticNumber"]

Block[{m,n},DeleteCases[{
#,
2,
GraphData[#,"FractionalChromaticNumber"]
}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&],{_,x_,x_}]]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Grid",{n,n}},"FractionalChromaticNumber"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["FractionalChromaticNumber"]

Block[{k,m,n},DeleteCases[{
#,
2,
GraphData[#,"FractionalChromaticNumber"]
}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==3&],{_,x_,x_}]]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Grid",{n,n,n}},"FractionalChromaticNumber"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"FractionalChromaticNumber"],{n,10}]

Table[GraphData[{"HalvedCube",n},"VertexTransitive"],{n,10}]

Table[GraphData[{"HalvedCube",n},"V"],{n,10}]

FindSequenceFunction[%,n]

A005864

Table[GraphData[{"HalvedCube",n},"α"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"FractionalChromaticNumber"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"FractionalChromaticNumber"],{n,3,20}]

Factor[((3(n-1)/2+1)/((n-1)/2))]

Table[Piecewise[{{3,Mod[n,2]==0},{((3n-1)/(n-1)),Mod[n,2]==1}}],{n,3,10}]

Hypercube

Entity["Graph",{"Hypercube",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Hypercube",n},"FractionalChromaticNumber"],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["FractionalChromaticNumber"]

Entity["Graph",{"Keller",n}]["IndependenceNumber"]

Entity["Graph",{"Keller",n}]["VertexCount"]

seq=Table[GraphData[{"Keller",n},"FractionalChromaticNumber"],{n,5}]

Table[GraphData[{"Keller",n},"VertexTransitive"],{n,5}]

FullSimplify[4^n/{4,5,2^n}]

Table[Piecewise[{{1,n==1},{16/5,n==2}},2^n],{n,5}]

King m×n

Block[{m,n},DeleteCases[{
#,
{m,n}=("King"/.GraphData[#,"NotationRules"]);Piecewise[{{1,m==n==1},{2,Min[m,n]==1}},4],
GraphData[#,"FractionalChromaticNumber"]
}&/@GraphData["King"],{_,x_,x_}]]

King n×n

Table[GraphData[{"King",{n,n}},"FractionalChromaticNumber"],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["FractionalChromaticNumber"]

Block[{m,n},DeleteCases[{
#,
{m,n}=("Knight"/.GraphData[#,"NotationRules"]);Piecewise[{{1, Min[m, n] == 1 || m == n == 2}}, 2],
GraphData[#,"FractionalChromaticNumber"]
}&/@GraphData["Knight"],{_,x_,x_}]]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["FractionalChromaticNumber"]//TraditionalForm

Table[GraphData[{"Knight",{n,n}},"FractionalChromaticNumber"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Ladder",n},"FractionalChromaticNumber"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"FractionalChromaticNumber"],{n,20}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"FractionalChromaticNumber"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"MoebiusLadder",n},"FractionalChromaticNumber"],{n,3,25}]

Mycielski

A073833/A073834

Entity["Graph",{"Mycielski",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Mycielski",n},"FractionalChromaticNumber"],{n,11}]

FindSequenceFunction[seq,n]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

RSolve[{a[1]==1,a[n]==a[n-1]+1/a[n-1]},a[n],n]

NestList[#+1/#&,1,5]

Transpose[NumeratorDenominator[%]]

RecurrenceTable[{\[FormalA][\[FormalN]]==\[FormalA][\[FormalN]-1]+1/\[FormalA][\[FormalN]-1],\[FormalA][1]==1},\[FormalA],{\[FormalN],10}]

Odd

Entity["Graph",{"Odd",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Odd",n},"FractionalChromaticNumber"],{n,7}]

Pasechnik

Do[Print[{{"Pasechnik",n},FindFractionalColoring[GraphData[{"Pasechnik",n}]]//Timing}],{n,5}]

Pan

seq=Table[GraphData[{"Pan",n},"FractionalChromaticNumber"],{n,3,20}]

Table[Piecewise[{{2,Mod[n,2]==0},{((2n)/(n-1)),Mod[n,2]==1}}],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["FractionalChromaticNumber"]

seq=Table[GraphData[{"Path",n},"FractionalChromaticNumber"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["FractionalChromaticNumber"]//TraditionalForm

seq=Table[GraphData[{"Prism",n},"FractionalChromaticNumber"],{n,3,25}]

Queen m×n

Block[{m,n},DeleteCases[{
#,
{m,n}=("Queen"/.GraphData[#,"NotationRules"]);Max[m,n],
GraphData[#,"FractionalChromaticNumber"]
}&/@GraphData["Queen"],{_,x_,x_}]]

Queen n×n

Table[GraphData[{"Queen",{n,n}},"FractionalChromaticNumber"],{n,20}]

Table[GraphData[{"Queen",{n,n}},"VertexTransitive"],{n,10}]

Table[GraphData[{"Queen",{n,n}},"α"],{n,10}]

Do[Print[{{"Queen",{n,n}},FractionalChromaticNumber[GraphData[{"Queen",{n,n}}]]//Timing}],{n,10}]

Rook m×n

Block[{m,n},DeleteCases[{
#,
{m,n}=("Rook"/.GraphData[#,"NotationRules"]);Max[m,n],
GraphData[#,"FractionalChromaticNumber"]
}&/@GraphData["Rook"],{_,x_,x_}]]

Rook n×n

Table[GraphData[{"Rook",{n,n}},"FractionalChromaticNumber"],{n,10}]

RookComplement m×n

Block[{m,n},DeleteCases[{
#,
{m,n}=("RookComplement"/.GraphData[#,"NotationRules"]);Min[m,n],
GraphData[#,"FractionalChromaticNumber"]
}&/@GraphData["RookComplement"],{_,x_,x_}]]

RookComplement n×n

Table[GraphData[{"RookComplement",{n,n}},"FractionalChromaticNumber"],{n,10}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"FractionalChromaticNumber"],{n,4}]

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"FractionalChromaticNumber"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"FractionalChromaticNumber"],{n,6}]

Star

Entity["Graph",{"Star",n}]["FractionalChromaticNumber"]

Table[GraphData[{"Star",n},"FractionalChromaticNumber"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"FractionalChromaticNumber"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"FractionalChromaticNumber"],{n,3,20}]

Table[Piecewise[{{2,Mod[n,2]==0},{((2n)/(n-1)),Mod[n,2]==1}}],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"FractionalChromaticNumber"],{n,6,10}]

Table[GraphData[{"Tetrahedral",n},"VertexTransitive"],{n,6,10}]

Table[GraphData[{"Tetrahedral",n},"V"],{n,6,10}]

FindSequenceFunction[%,n-5]//Factor

Binomial[n,3]

Table[GraphData[{"Tetrahedral",n},"α"],{n,6,10}]

FindSequenceFunction[%,n-5]//Factor

Table[(6 n^2-9 n-10-3 (-1)^n (n-2)-6 Cos[n Pi/3]+10 Cos[2 n Pi/3]+10 Sqrt[3] Sin[n Pi/3]+6 Sqrt[3] Sin[2 n Pi/3])/36,{n,6,10}]

Table[Binomial[n,3]/((6 n^2-9 n-10-3 (-1)^n (n-2)-6 Cos[n Pi/3]+10 Cos[2 n Pi/3]+10 Sqrt[3] Sin[n Pi/3]+6 Sqrt[3] Sin[2 n Pi/3])/36),{n,6,10}]

Transposition

Entity["Graph",{"Transposition",n}]["FractionalChromaticNumber"]

Table[GraphData[{"Transposition",n},"FractionalChromaticNumber"],{n,5}]

Triangular

seq=Table[GraphData[{"Triangular",n},"FractionalChromaticNumber"],{n,5,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"FractionalChromaticNumber"],{n,0,10}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"FractionalChromaticNumber"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"FractionalChromaticNumber"],{n,4,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"FractionalChromaticNumber"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"FractionalChromaticNumber"],{n,10}]

Web

seq=Table[GraphData[{"Web",n},"FractionalChromaticNumber"],{n,3,20}]

Table[Piecewise[{{2,Mod[n,2]==0},{((2n)/(n-1)),Mod[n,2]==1}}],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["FractionalChromaticNumber"]//TraditionalForm

seq=Table[GraphData[{"Wheel",n},"FractionalChromaticNumber"],{n,4,20}]

FindSequenceFunction[seq[[;;;;2]],n/2-1]//Factor

Table[Piecewise[{{((3 n-4)/(n-2)),Mod[n,2]==0},{3,Mod[n,2]==1}}],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"FractionalChromaticNumber"],{n,2,10}]

Algorithm comparison

MaximalIndependentVertexSets vs IndependentVertexSets

10

Length[gs=GraphData["Connected",;;10]]

cns=GraphData[#,"FractionalChromaticNumber"]&/@gs;

colorings1=Monitor[FractionalChromaticNumber[GraphData[g=#],"IndependentSets"->FindAllMaximalIndependentVertexSets]&/@gs,g];//Timing

colorings2=Monitor[FractionalChromaticNumber[GraphData[g=#],"IndependentSets"->FindAllIndependentVertexSets]&/@gs,g];//Timing

DeleteCases[Transpose[{gs,cns,colorings1,colorings2}],{_,x_,x_,x_}]