Fractional Edge Chromatic Number

Author

Eric W. Weisstein
January 1, 2024

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

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

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

Table

GraphDataCountTable["FractionalEdgeChromaticNumber"]

Missing

DateString[]

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

Length[missing]

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

Parametrized families

<<MathWorld`Graphs`

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"FractionalEdgeChromaticNumber"],{n,20}]

Table[3n/2-1,{n,2,10,2}]

Table[n/2(6n/2-1),{n,2,10,2}]

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

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

Antiprism

Entity["Graph",{"Antiprism",n}]["FractionalEdgeChromaticNumber"]

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

Apollonian

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

FindSequenceFunction[seq,n]

Barbell

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

Bishop n×n

A042948

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

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

BlackBishop n×n

A042948

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

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

Book

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

Centipede

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

CocktailParty

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

Complete

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

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

CompleteBipartite m×n

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

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

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

Table[GraphData[{"CompleteTripartite",{k,m,n}},"Symmetric"],{n,10},{m,n},{k,m}]

CompleteTripartite n×n×n

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

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

Table[GraphData[{"CompleteTripartite",{n,n,n}},"Symmetric"],{n,10}]

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

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

{((2 3(n^2))/(3n-1)),((2 3(n^2))/(3n))}//Factor

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

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

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

Cycle

Entity["Graph",{"Cycle",n}]["FractionalEdgeChromaticNumber"]

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

Empty

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

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

FibonacciCube

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

FoldedCube

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

Gear

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

Grid m×n

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

Block[{m,n},DeleteCases[{
#,
{m,n}=("Grid"/.GraphData[#,"NotationRules"]);Piecewise[{{0,m==n==1},{2,m==n==2},{3,Min[m,n]==2}},4],
GraphData[#,"FractionalEdgeChromaticNumber"]
}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&],{_,x_,x_}]]

Grid n×n

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

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

Grid k×m×n

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

Block[{k,m,n},DeleteCases[{
#,
{k,m,n}=("Grid"/.GraphData[#,"NotationRules"]);Piecewise[{{0,k==m==n==1},{3,k==m==n==2},
{4,Min[k,m,n]==2&&Max[k,m,n]<=5},{5,Min[k,m,n]==2&&Max[k,m,n]>=6}},6],
GraphData[#,"FractionalEdgeChromaticNumber"]
}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==3&],{_,x_,x_}]]

Grid n×n×n

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

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

HalvedCube

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

FindSequenceFunction[seq,n]

Hanoi

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

Helm

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

Hypercube

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

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

Keller

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

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

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

Table[-(3^n)+(4^n)-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[#,"FractionalEdgeChromaticNumber"]
}&/@GraphData["King"],{_,x_,x_}]]

King n×n

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

Knight m×n

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

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

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["FractionalEdgeChromaticNumber"]

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

Ladder

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

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

LadderRung

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

MengerSponge

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

MoebiusLadder

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

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

Mycielski

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

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

Odd

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

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

Pan

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

Pasechnik

Do[Print[{{"Pasechnik",n},FractionalChromaticNumber[LineGraph@GraphData[{"Pasechnik",n}]]//Timing}],{n,5}]

...out of memory...

Path

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

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

Prism

Entity["Graph",{"Prism",n}]["FractionalEdgeChromaticNumber"]

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

Queen m×n

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

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"FractionalEdgeChromaticNumber"],{n,10}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

Rook m×n

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

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"FractionalEdgeChromaticNumber"],{n,10}]

FindSequenceFunction[seq[[2;;;;2]],n/2]

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

RookComplement m×n

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

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"FractionalEdgeChromaticNumber"],{n,10}]

FindSequenceFunction[seq[[;;;;2]],n]

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

Table[(n+1)/2,{n,1,10,2}]

Factor[(((n-1)/2*(2*(n-1)/2+1)^2)/((n+1)/2))]

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

SierpinskiCarpet

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

SierpinskiSieve

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

SierpinskiTetrahedron

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

Star

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

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

Sun

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

Sunlet

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

Tetrahedral

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

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

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

FindSequenceFunction[%,n-5]//Factor

Table[Binomial[n,3],{n,6,20}]

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

FindSequenceFunction[%,n-5]//Factor

Table[6Binomial[n,4],{n,6,10}]

With[{mm=6Binomial[n,4],nn=Binomial[n,3]},2mm/{nn-1,nn}]//Factor

Table[Piecewise[{{((3 (-2+n) (-1+n) n)/(2+(n^2))),Mod[n,4]==3}},3 (-3+n)],{n,6,10}]

Transposition

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

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

Table[n(n-1)/2,{n,5}]

Table[Binomial[n,2],{n,5}]

Triangular

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

Table[GraphData[{"Triangular",n},"Symmetric"],{n,5,20}]

Table[GraphData[{"Triangular",n},"V"],{n,5,20}]

FindSequenceFunction[%,n-4]//Factor

Table[Binomial[n,2],{n,5,20}]

Table[Mod[n,4],{n,5,20}]

Table[GraphData[{"Triangular",n},"EdgeCount"],{n,5,10}]

FindSequenceFunction[%,n-4]//Factor

Binomial[n,3]

Table[3Binomial[n,3],{n,5,10}]

With[{mm=3Binomial[n,3],nn=Binomial[n,2]},2mm/{nn-1,nn}]//Factor

Table[Piecewise[{{((2 (-1+n) n)/(1+n)),Mod[n,4]==2||Mod[n,4]==3}},2 (-2+n)],{n,5,10}]

TriangularGrid

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

TriangularHoneycombAcuteKnight

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

Table[GraphData[{"TriangularHoneycombQueen",n},"Connected"],{n,10}]

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

Do[Print[{{"TriangularHoneycombQueen",n},FractionalChromaticNumber[LineGraph@GraphData[{"TriangularHoneycombQueen",n}]]//Timing}],{n,10}]

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

Total/@data[[All,-1,-1,All,-1]]

TriangularHoneycombRook

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

Web

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

Wheel

Entity["Graph",{"Wheel",n}]["FractionalEdgeChromaticNumber"]

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

WhiteBishop n×n

A042963

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

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

Computing

Stan Wagom, 5/17/2012:

The fact that there is a poly. time alg. for this is fascinating so, in theory, we might be able to get it for all your graphs.

Remember:

If Edge Chrom = d (max degree), then Frac Edge Chrom = d.

So that is where one starts and will get 60% or so of them. 

And then if FracEdgeChrom > d, one will know that Edge Chrom = d+1.

There are very few examples where Edge Chrom is d+1 and FracEdgeChrom = d, and I suspect that, in your database, all such are small.

Tests

l1=Select[GraphData["EdgeChromaticNumber","Defined"],(ecn=GraphData[#,"EdgeChromaticNumber"])===Max[GraphData[#,"Degrees"]]&&ecn=!=GraphData[#,"FractionalEdgeChromaticNumber"]&]

l2=Select[GraphData["Class1"],GraphData[#,"EdgeChromaticNumber"]=!=GraphData[#,"FractionalEdgeChromaticNumber"]&]

l1==l2