Q-Chromatic Polynomial

Author

Eric W. Weisstein
July 20, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Q-ChromaticPolynomial.nb.

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

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

Classes

Andrasfai

(poly=Factor@Table[GraphData[{"Andrasfai",n},"QChromaticPolynomial"][x],{n,k0=1,6}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,4]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Antiprism

Entity["Graph",{"Antiprism",n}]["QChromaticPolynomial"][x]

Entity["Graph",{"Antiprism",n}]["ChromaticPolynomial"][x]

Select[GraphData["Antiprism"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=Table[GraphData[{"Antiprism",n},"QChromaticPolynomial"],{n,3,25}]/.f_Function:>f[x]

r=Factor@FindPolynomialRecurrence[poly,4]

Factor/@LinearRecurrence[r,Take[poly,Length[r]],8]

%==poly

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

RSolve[{p[n,x]==(10-6x+x^2)p[n-1,x]+(-33+38x-15x^2+2x^3)p[n-2,x]+(40-64x+38x^2-10x^3+x^4)p[n-3,x]+(-16+32x-24x^2+8x^3-x^4)p[n-4,x],
p[3,x]==(-2+x) (-1+x) x (-32+29 x-9 (x^2)+(x^3)),p[4,x]==(-3+x) (-2+x) (-1+x) x (71-84 x+41 (x^2)-10 (x^3)+(x^4)),p[5,x]==(-3+x) (-2+x) (-1+x) x (398-723 x+599 (x^2)-290 (x^3)+85 (x^4)-14 (x^5)+(x^6)),p[6,x]==(-2+x) (-1+x) x (-6143+17177 x-22824 (x^2)+18887 (x^3)-10623 (x^4)+4159 (x^5)-1121 (x^6)+199 (x^7)-21 (x^8)+(x^9))},p[n,x],n]//FullSimplify

Table[(2^(-n)) ((2^n)-(((5-(Sqrt[9-4 x])-2 x))^n)-(((5+(Sqrt[9-4 x])-2 x))^n)+(2^n) ((((((-2+x))^2)))^n)+x (-3 (2^n)+(((5-(Sqrt[9-4 x])-2 x))^n)+(((5+(Sqrt[9-4 x])-2 x))^n)+(2^n) x)),{n,3,8}]//Expand

(2^(-n)) ((2^n)-(((5-(Sqrt[9-4 x])-2 x))^n)-(((5+(Sqrt[9-4 x])-2 x))^n)+(2^n) ((((((-2+x))^2)))^n)+x (-3 (2^n)+(((5-(Sqrt[9-4 x])-2 x))^n)+(((5+(Sqrt[9-4 x])-2 x))^n)+(2^n) x))//TraditionalForm

(2^(-n)) ((2^n)-(((5-(Sqrt[9-4 x])-2 x))^n)-(((5+(Sqrt[9-4 x])-2 x))^n)+(2^n) ((((((-2+x))^2)))^n)+x (-3 (2^n)+(((5-(Sqrt[9-4 x])-2 x))^n)+(((5+(Sqrt[9-4 x])-2 x))^n)+(2^n) x))/.{(5-(Sqrt[9-4 x])-2 x)->s,(5+(Sqrt[9-4 x])-2 x)->t}//FullSimplify

(2^(-n)) (-1+x)((s^n)+(t^n) )+(1+(((-2+x))^(2n))+(-3+x) x)//TraditionalForm

p-Table[(2^(-n)) (-1+x)((s^n)+(t^n) )+(1+(((-2+x))^(2n))+(-3+x) x)/.{s->(5-(Sqrt[9-4 x])-2 x),t->(5+(Sqrt[9-4 x])-2 x)},{n,3,8}]//Expand

Apollonian

p=DeleteCases[Table[GraphData[{"Apollonian",n},"QChromaticPolynomial"][x],{n,4}],_Missing[x]]

Factor/@FindPolynomialRecurrence[p,2]

Barbell

Subtract@@@Table[{
(x-1)/x GraphData[{"Complete",n},"QChromaticPolynomial"][x]^2,
GraphData[{"Barbell",n},"QChromaticPolynomial"][x]
},{n,3,20}]

Select[GraphData["Barbell"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

Bishop n×n

p=DeleteCases[Table[GraphData[{"Bishop",{n,n}},"QChromaticPolynomial"][x],{n,2,6}],(_GraphData|_Missing)[x]]//Quiet

BlackBishop m×n

Select[GraphData["BlackBishop"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

BlackBishop n×n

Select[GraphData["BlackBishop"],Equal@@("BlackBishop"/.GraphData[#,"NotationRules"])&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"BlackBishop",{n,n}},"QChromaticPolynomial"][x],{n,2,6}],(_GraphData|_Missing)[x]]//Quiet

Factor@FindPolynomialRecurrence[p,4]

Factor@FindPolynomialRecurrence[p,5]

Book

Select[GraphData["Book"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=Table[GraphData[{"Book",n},"QChromaticPolynomial"][x],{n,3,10}]

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

p-Table[(x-1)x(3-3x+x^2)^n,{n,3,9}]//Expand

Bruhat

(poly=Table[GraphData[{"Bruhat",n},"QChromaticPolynomial"],{n,6}]/.f_Function:>f[x])//Column

Caveman

Select[GraphData["Caveman"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

Centipede

poly=Table[GraphData[{"Centipede",n},"QChromaticPolynomial"][x],{n,3,10}]

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

CocktailParty

Select[GraphData["CocktailParty"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"CocktailParty",n},"QChromaticPolynomial"][x],{n,20}],_Missing[x]]

r=Factor@FindPolynomialRecurrence[p,6]

r=Factor@FindPolynomialRecurrence[p,8]

r=Factor@FindPolynomialRecurrence[p,10]

Complete

Entity["Graph",{"Complete",n}]["QChromaticPolynomial"][x]

Select[GraphData["Complete"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

(poly=Table[GraphData[{"Complete",n},"QChromaticPolynomial"]/.f_Function:>Factor@f[x],{n,20}])//ColumnForm//TraditionalForm

(Piecewise[{{Missing["NotApplicable"],n==1||n==2},{1/#,n==3},{1,n==4}},FactorialPower[#-1,n-4]]&)

%[x]

With[{n=1},(Piecewise[{{Missing["NotApplicable"],n==1||n==2},{1/#,n==3},{1,n==4}},FactorialPower[#-1,n-4]]&)][x]

Table[FunctionExpand@FactorialPower[x-1,n-4],{n,8}]//ColumnForm//TraditionalForm

r=Factor/@FindLinearRecurrence[poly]

CompleteBipartite m×n

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

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["QChromaticPolynomial"][x]

Select[GraphData["CompleteBipartite"],Equal@@("CompleteBipartite"/.GraphData[#,"NotationRules"])&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"CompleteBipartite",{n,n}},"QChromaticPolynomial"][x],{n,3,10}],_Missing[x_]]

r=FindPolynomialRecurrence[p,3]

r=FindPolynomialRecurrence[p,4]

r=FindPolynomialRecurrence[p,5]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["QChromaticPolynomial"][x]

Select[GraphData["CompleteTripartite"],Equal@@("CompleteTripartite"/.GraphData[#,"NotationRules"])&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"CompleteTripartite",{n,n,n}},"QChromaticPolynomial"][x],{n,3,10}],(_GraphData|_Missing)[x]]

r=Factor/@FindPolynomialRecurrence[p,3]

Cone

Select[GraphData[class="Cone"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

CrossedPrism

Select[GraphData["CrossedPrism"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=Table[GraphData[{"CrossedPrism",n},"QChromaticPolynomial"][x],{n,4,17,2}]

r=FindPolynomialRecurrence[p,3]

r=FindPolynomialRecurrence[p,4]

Crown

Select[GraphData["Crown"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"Crown",n},"QChromaticPolynomial"][x],{n,3,10}],_Missing[x]]

r=FindPolynomialRecurrence[p,3]

r=FindPolynomialRecurrence[p,4]

CubeConnectedCycle

Select[GraphData["CubeConnectedCycle"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=Table[GraphData[{"CubeConnectedCycle",n},"QChromaticPolynomial"][x],{n,3,6}]

r=FindLinearRecurrence[p]

Cycle

Entity["Graph",{"Cycle",n}]["QChromaticPolynomial"][x]

(poly=Table[GraphData[{"Cycle",n},"QChromaticPolynomial"]/.f_Function:>f[x],{n,3,20}])//Column//TraditionalForm

Entity["Graph",{"Cycle",n}]["ChromaticPolynomial"][x]

Table[(((((x+2))^(n-1))-1)/(x(x+1)(x+3))),{n,3,20,2}]//Factor//Expand//Column//TraditionalForm

Table[Function[x,Piecewise[{{((x+2)^(n-1)-1)/(x (x+1) (x+3)),Mod[n,2]==1}},Missing["NotApplicable"]]][x],{n,3,10}]

CycleComplement

poly=Table[GraphData[{"CycleComplement",n},"QChromaticPolynomial"]/.f_Function:>f[x],{n,3,20}]

Do[Print[{i,FindLinearRecurrence[Drop[DeleteMissing@poly,i]]//Head//Timing}],{i,0,6}]

DiagonalIntersection

(poly=Table[GraphData[{"DiagonalIntersection",n},"QChromaticPolynomial"],{n,3,14}]/.f_Function:>f[x])//Column

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

RSolve[{p[x,n]==(x-2)p[x,n-1]+(x-1)p[x,n-2],p[x,3]==x^3-3x^2+2x,p[x,4]==x^4-4x^3+6x^2-3x},p[x,n],n]

FullSimplify[-(((-1))^n)+(((-1+x))^n)+(((-1))^n) x,n∈Integers&&n>2]

p[x,3]:=x^3-3x^2+2x
p[x,4]:=x^4-4x^3+6x^2-3x
p[x,n_]:=(x-2)p[x,n-1]+(x-1)p[x,n-2]

Table[p[x,n],{n,3,7}]//Expand//Column//TraditionalForm

Table[(((-1))^n) (-1+x)+(((-1+x))^n),{n,3,10}]//Expand//Column//TraditionalForm

Dipyramid

(poly=Table[GraphData[{"Dipyramid",n},"QChromaticPolynomial"],{n,n0=3,20}]/.f_Function:>f[x])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[coef]}],p[n,x]==coef.Table[p[n-k,x],{k,Length[coef]}]],p[n,x],n]//FullSimplify

Table[x ((((-1))^n)-(((-3+x))^n)+(((-2+x))^n)+((((-1))^n) (-3+x)+(((-3+x))^n)) x),{n,3,5}]//Factor//Column

Empty

Entity["Graph",{"Empty",n}]["QChromaticPolynomial"][x]

Select[GraphData[class="Empty"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=DeleteCases[Table[GraphData[{class,n},"QChromaticPolynomial"][x],{n,n0=1,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[r]}],p[n,x]==r.Table[p[n-k,x],{k,Length[r]}]],p[n,x],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"QChromaticPolynomial"],{n,15}]/.f_Function:>f[x]//Column

Firecracker

Select[GraphData["Firecracker"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

FoldedCube

Select[GraphData["FoldedCube"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

(p=Table[GraphData[{"FoldedCube",n},"QChromaticPolynomial"],{n,2,10}]/.f_Function:>f[x])//Column

r=FindLinearRecurrence[p,2]

Forest

Select[GraphData["Forest"],Expand[Subtract@@{
GraphData[#,"QChromaticPolynomial"][x],
(-1)^({1,-1}.GraphData[#,{"V","C"}])x^GraphData[#,"C"](1-x)^GraphData[#,"E"]}]=!=0&]

Gear

p=Table[GraphData[{"Gear",n},"QChromaticPolynomial"][x],{n,3,10}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(-3+3 x-(x^2)) p[-2+n,x]+(4-3 x+(x^2)) p[-1+n,x],
p[3,x]==(-1+x) x (5-4 x+(x^2)) (-5+7 x-4 (x^2)+(x^3)),p[4,x]==(-1+x) x (-79+244 x-350 (x^2)+298 (x^3)-161 (x^4)+55 (x^5)-11 (x^6)+(x^7))},p[n,x],n]//FullSimplify

Factor[%]

p-Table[x (-2+x+(((3-3 x+(x^2)))^n)),{n,3,10}]//Expand

Grid m×n

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

Grid n×n

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

Select[GraphData["Grid"],Length[n="Grid"/.GraphData[#,"NotationRules"]]==2&&Equal@@n&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"Grid",{n,n}},"QChromaticPolynomial"][x],{n,20}],(_Missing|_GraphData)[x]]//Quiet

FindPolynomialRecurrence[p,3]

FindPolynomialRecurrence[p,4]

Grid k×m×n

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

Grid n×n×n

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

Select[GraphData["Grid"],Length[n="Grid"/.GraphData[#,"NotationRules"]]==3&&Equal@@n&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=Table[GraphData[{"Grid",{n,n,n}},"QChromaticPolynomial"][x],{n,3}]

FindLinearRecurrence[p]

HalvedCube

Select[GraphData["HalvedCube"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=Table[GraphData[{"HalvedCube",n},"QChromaticPolynomial"][x],{n,5}]

r=FindPolynomialRecurrence[p,2]

r=FindPolynomialRecurrence[p,3]

Hanoi

(p=Table[GraphData[{"Hanoi",n},"QChromaticPolynomial"],{n,5}]/.f_Function:>f[x])//Column

r=FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

Helm

Select[GraphData["Helm"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=Table[GraphData[{"Helm",n},"QChromaticPolynomial"][x],{n,3,10}]//Factor

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

RSolve[{p[n,x]==(3-4x+x^2)p[n-1,x]+(-2+5x-4x^2+x^3)p[n-2,x],
p[3,x]==(-3+x) (-2+x) (((-1+x))^4) x,p[4,x]==(-2+x) (((-1+x))^5) x (7-5 x+(x^2))},p[n,x],n]//FullSimplify

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

Factor[2-3 x+(x^2)]

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

Hypercube

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

Select[GraphData["Hypercube"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"Hypercube",n},"QChromaticPolynomial"][x],{n,10}],_Missing[x]]

FindPolynomialRecurrence[p,3]

Keller

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

Select[GraphData[class="Keller"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=DeleteCases[Table[GraphData[{class,n},"QChromaticPolynomial"][x],{n,n0=1,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindPolynomialRecurrence[poly,2]

(Subscript[p, n])[x]==r.Table[(Subscript[p, n-k])[x],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[r]}],p[n,x]==r.Table[p[n-k,x],{k,Length[r]}]],p[n,x],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

King

Select[GraphData["King"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

King n×n

Select[GraphData["King"],Equal@@("King"/.GraphData[#,"NotationRules"])&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"King",{n,n}},"QChromaticPolynomial"][x],{n,2,6}],_Missing[x]]

Factor@FindPolynomialRecurrence[p,4]

Knight m×n

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

Knight n×n

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

Select[GraphData["Knight"],Equal@@("Knight"/.GraphData[#,"NotationRules"])&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"Knight",{n,n}},"QChromaticPolynomial"][x],{n,2,10}],_Missing[x]]

FindPolynomialRecurrence[p,3]

Ladder

Entity["Graph",{"Ladder",n}]["QChromaticPolynomial"][x]

(poly=Factor@Table[GraphData[{"Ladder",n},"IndependencePolynomial"][x],{n,k0=1,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

LadderRung

poly=Table[GraphData[{"LadderRung",n},"QChromaticPolynomial"][x],{n,20}]

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

Table[(-1+x)^n x^n,{n,20}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["QChromaticPolynomial"][x]

Select[GraphData["MoebiusLadder"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

(poly=Table[GraphData[{"MoebiusLadder",n},"QChromaticPolynomial"],{n,3,25}]/.f_Function:>f[x])//Column

r=Factor/@FindLinearRecurrence[poly]

r=Factor@FindPolynomialRecurrence[poly,4]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

RSolve[a[n]==(8-5 x+(x^2))a[n-1]+(-22+27 x-12 (x^2)+2 (x^3))a[n-2]+(24-43 x+29 (x^2)-9 (x^3)+(x^4))a[n-3]+(-9+21 x-18 (x^2)+7 (x^3)-(x^4))a[n-4]&&a[3]==(-1+x) x (31-47 x+28 (x^2)-8 (x^3)+(x^4))&&a[4]==(-2+x) (-1+x) x (5-4 x+(x^2)) (-14+12 x-5 (x^2)+(x^3))&&a[5]==(-1+x) x (573-1602 x+2108 (x^2)-1717 (x^3)+946 (x^4)-359 (x^5)+91 (x^6)-14 (x^7)+(x^8))&&a[6]==(-2+x) (-1+x) x (-1097+3225 x-4689 (x^2)+4399 (x^3)-2898 (x^4)+1372 (x^5)-462 (x^6)+106 (x^7)-15 (x^8)+(x^9)),a[n],n]//FullSimplify

Table[-1+(((1-x))^n)-(((3-x))^n)+(-(((1-x))^n)+(((3-x))^n)) x+(((3+(-3+x) x))^n),{n,3,10}]//Factor

Mycielski

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

Select[GraphData["Mycielski"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=Table[GraphData[{"Mycielski",n},"QChromaticPolynomial"][x],{n,4}]

r=FindLinearRecurrence[p]

Odd

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

Select[GraphData["Odd"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

(poly=Table[GraphData[{"Odd",n},"QChromaticPolynomial"],{n,2,5}]/.f_Function:>f[x])//Column

r=Factor/@FindLinearRecurrence[p]

Pan

Select[GraphData["Pan"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=Table[GraphData[{"Pan",n},"QChromaticPolynomial"][x],{n,3,7}]

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

RSolve[{p[n,x]==(-1+x) p[-2+n,x]+(-2+x) p[-1+n,x],
p[3,x]==(-2+x) (((-1+x))^2) x,
p[4,x]==(((-1+x))^2) x (3-3 x+(x^2))},p[n,x],n]//FullSimplify

p-Table[(((-1))^n) (((-1+x))^2)+(((-1+x))^(1+n)),{n,3,7}]//Expand

Path

Entity["Graph",{"Path",n}]["QChromaticPolynomial"][x]

poly=Table[GraphData[{"Path",n},"QChromaticPolynomial"][x],{n,20}]

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

Table[x(((-1+x))^(n-1)),{n,20}]

PathComplement

poly=Table[GraphData[{"PathComplement",n},"QChromaticPolynomial"]/.f_Function:>f[x],{n,20}]

Do[Print[{i,FindLinearRecurrence[Drop[DeleteMissing@poly,i]]//Head//Timing}],{i,0,6}]

poly2=Factor/@Table[((poly[[i]])/(FactorialPower[x,Ceiling[i/2]]//FunctionExpand)),{i,17}]

Do[Print[{i,FindLinearRecurrence[Drop[DeleteMissing@poly2,i]]//Head//Timing}],{i,0,6}]

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Prism

Entity["Graph",{"Prism",n}]["QChromaticPolynomial"][x]

Select[GraphData["Prism"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

(poly=Table[GraphData[{"Prism",n},"QChromaticPolynomial"][x],{n,3,11}])//Column

r=FindPolynomialRecurrence[poly,4]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

LinearRecurrence[{8-5 x+(x^2),(-2+x) (11-8 x+2 (x^2)),24-43 x+29 (x^2)-9 (x^3)+(x^4),-(-3+x) (-1+x) (3-3 x+(x^2))},{(-2+x) (-1+x) x (-13+14 x-6 (x^2)+(x^3)),(-1+x) x (133-290 x+282 (x^2)-159 (x^3)+55 (x^4)-11 (x^5)+(x^6)),(-2+x) (-1+x) x (-282+650 x-719 (x^2)+494 (x^3)-225 (x^4)+67 (x^5)-12 (x^6)+(x^7)),(-1+x) x (2183-7517 x+12563 (x^2)-13457 (x^3)+10183 (x^4)-5640 (x^5)+2296 (x^6)-674 (x^7)+136 (x^8)-17 (x^9)+(x^10))},9]//Factor//Column

RSolve[{poly[n,x]==(-9+21 x-18 (x^2)+7 (x^3)-(x^4)) poly[-4+n,x]+(24-43 x+29 (x^2)-9 (x^3)+(x^4)) poly[-3+n,x]+(-22+27 x-12 (x^2)+2 (x^3)) poly[-2+n,x]+(8-5 x+(x^2)) poly[-1+n,x],
poly[3,x]==(-2+x) (-1+x) x (-13+14 x-6 (x^2)+(x^3)),poly[4,x]==(-1+x) x (133-290 x+282 (x^2)-159 (x^3)+55 (x^4)-11 (x^5)+(x^6)),poly[5,x]==(-2+x) (-1+x) x (-282+650 x-719 (x^2)+494 (x^3)-225 (x^4)+67 (x^5)-12 (x^6)+(x^7)),poly[6,x]==(-1+x) x (2183-7517 x+12563 (x^2)-13457 (x^3)+10183 (x^4)-5640 (x^5)+2296 (x^6)-674 (x^7)+136 (x^8)-17 (x^9)+(x^10))},poly[n,x],n]//FullSimplify

poly-Table[1-(((1-x))^n)-(((3-x))^n)+x (-3+(((1-x))^n)+(((3-x))^n)+x)+(((3+(-3+x) x))^n),{n,3,9}]//Expand

-(((1-x))^n)-(((3-x))^n)+((((x-3) x+3))^n)+x ((((1-x))^n)+(((3-x))^n)+x-3)+1

Queen n×n

Select[GraphData["Queen"],Equal@@("Queen"/.GraphData[#,"NotationRules"])&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"Queen",{n,n}},"QChromaticPolynomial"][x],{n,2,20}],(_GraphData|_Missing)[x]]//Quiet

Factor@FindPolynomialRecurrence[p,3]

Factor@FindPolynomialRecurrence[p,4]

Rook n×n

(p=Table[GraphData[{"Rook",{n,n}},"QChromaticPolynomial"],{n,10}]/.f_Function:>f[x])//Column

r=FindPolynomialRecurrence[p,3]

RookComplement n×n

(Table[GraphData[{"RookComplement",{n,n}},"QChromaticPolynomial"],{n,10}]/.f_Function:>f[x])//Column

SierpinskiCarpet

Select[GraphData["SierpinskiCarpet"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=Table[GraphData[{"SierpinskiCarpet",n},"QChromaticPolynomial"][x],{n,3}]//Factor

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

SierpinskiSieve

Select[GraphData["SierpinskiSieve"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"SierpinskiSieve",n},"QChromaticPolynomial"][x],{n,10}],(_GraphData|_Missing)[x]]//Quiet

FindPolynomialRecurrence[p,3]

StackedBook

Select[GraphData["StackedBook"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

Star

Entity["Graph",{"Star",n}]["QChromaticPolynomial"][x]

poly=Table[GraphData[{"Star",n},"QChromaticPolynomial"],{n,3,20}]

QChromaticPolynomial[#,x]&/@Table[GraphData[{"Star",n},"ChromaticPolynomial"][x],{n,3,5}]

Sun

Select[GraphData["Sun"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=Table[GraphData[{"Sun",n},"QChromaticPolynomial"][x],{n,3,20}]

r=Factor/@FindPolynomialRecurrence[poly,4]

ToPolynomialRecurrence[p,x,n,r]

poly-Table[FactorialPower[x,n](x-2)^n//FunctionExpand,{n,3,10}]

Sunlet

Select[GraphData["Sunlet"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=Table[GraphData[{"Sunlet",n},"QChromaticPolynomial"][x],{n,3,20}]

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

RSolve[{p[n,x]==(-1+3 x-3 (x^2)+(x^3)) p[-2+n,x]+(2-3 x+(x^2)) p[-1+n,x],p[3,x]==(-2+x) (((-1+x))^4) x,p[4,x]==(((-1+x))^5) x (3-3 x+(x^2))},p[n,x],n]//FullSimplify

poly-Table[-(((1-x))^(1+n))+((((((-1+x))^2)))^n),{n,3,12}]//Expand

Tetrahedral

Select[GraphData["Tetrahedral"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"Tetrahedral",n},"QChromaticPolynomial"][x],{n,10}]//Quiet,(_GraphData|_Missing)[x]]

TorusGrid n×n

(poly=Factor@Table[GraphData[{"TorusGrid",{n,n}},"IndependencePolynomial"][x],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Transposition

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

(poly=Table[GraphData[{"Transposition",n},"QChromaticPolynomial"],{n,6}]/.f_Function:>f[x])//Column

Triangular

Select[GraphData["Triangular"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=Table[GraphData[{"Triangular",n},"QChromaticPolynomial"][x],{n,2,6}]

r=FindPolynomialRecurrence[p,2]

r=FindPolynomialRecurrence[p,3]

TriangularGrid

Select[GraphData[class="TriangularGrid"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=DeleteCases[Table[GraphData[{class,n},"QChromaticPolynomial"][x],{n,n0=1,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindPolynomialRecurrence[poly,3]

r=Factor/@FindPolynomialRecurrence[poly,4]

(Subscript[p, n])[x]==r.Table[(Subscript[p, n-k])[x],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[r]}],p[n,x]==r.Table[p[n-k,x],{k,Length[r]}]],p[n,x],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

TriangularHoneycombAcuteKnight

(poly=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"QChromaticPolynomial"],{n,n0=1,20}]/.f_Function:>f[x])//Column

r=Factor/@FindPolynomialRecurrence[poly,2]

r=Factor/@FindPolynomialRecurrence[poly,3]

r=Factor/@FindPolynomialRecurrence[poly,4]

(Subscript[p, n])[x]==r.Table[(Subscript[p, n-k])[x],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[r]}],p[n,x]==r.Table[p[n-k,x],{k,Length[r]}]],p[n,x],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

TriangularHoneycombObtuseKnight

Select[GraphData[class="TriangularHoneycombObtuseKnight"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=DeleteCases[Table[GraphData[{class,n},"QChromaticPolynomial"][x],{n,n0=4,20}],_Missing[_]]

r=Factor/@FindPolynomialRecurrence[poly,2]

r=Factor/@FindPolynomialRecurrence[poly,3]

(Subscript[p, n])[x]==r.Table[(Subscript[p, n-k])[x],{k,Length[r]}]//TraditionalForm

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[r]}],p[n,x]==r.Table[p[n-k,x],{k,Length[r]}]],p[n,x],n]//FullSimplify

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

TriangularHoneycombQueen

(poly=Table[GraphData[{"TriangularHoneycombQueen",n},"QChromaticPolynomial"],{n,n0=1,10}]/.f_Function:>f[x])//Column

r=Factor/@FindPolynomialRecurrence[poly,2]

r=Factor/@FindPolynomialRecurrence[poly,3]

TriangularHoneycombRook

Select[GraphData[class="TriangularHoneycombRook"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=DeleteCases[Table[GraphData[{class,n},"QChromaticPolynomial"][x],{n,n0=1,20}],(_GraphData|_Missing)[_]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

r=Factor/@FindPolynomialRecurrence[poly,4]

Product[(((x-k))^(n-k)),{k,0,n}]//FullSimplify

Table[Product[(((x-k))^(n-k)),{k,0,n}],{n,3}]

Product[FactorialPower[x,k],{k,3}]//FunctionExpand

(∏_(k=1)^n)(FactorialPower[x, k])

FullSimplify[Product[FactorialPower[x,k],{k,n}]]

Table[(I^(n (3+n))) (x^n) ((BarnesG[1-x])^(-1+n)) ((BarnesG[2-x])^(-n)) BarnesG[1+n-x],{n,3}]//FullSimplify

FullSimplify[Subtract@@{-(((x^2) BarnesG[1-x] BarnesG[3-x])/((BarnesG[2-x])^2)),(-1+x) (x^2)}]//FunctionExpand

Plot[ (1-x-((BarnesG[1-x] BarnesG[3-x])/((BarnesG[2-x])^2))),{x,-1,5}]

Web

Select[GraphData["Web"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=DeleteCases[Table[GraphData[{"Web",n},"QChromaticPolynomial"][x],{n,10}],(_GraphData|_Missing)[x]]//Quiet

r=Factor/@FindLinearRecurrence[poly]

r=Factor/@FindPolynomialRecurrence[poly,4]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

n0=3;

soln=RSolve[Prepend[Table[p[n+n0-1,x]==poly[[n]],{n,Length[r]}],p[n,x]==r.Table[p[n-k,x],{k,Length[r]}]],p[n,x],n]//FullSimplify

soln[[1,1,2]]//TraditionalForm

Expand[Subtract@@@Table[{soln[[1,1,2]],poly[[n-n0+1]]},{n,n0+1,10}]]

Wheel

Entity["Graph",{"Wheel",n}]["QChromaticPolynomial"][x]

Select[GraphData["Wheel"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

poly=Table[GraphData[{"Wheel",n},"QChromaticPolynomial"][x],{n,4,20}]

r=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,r]

FormattedPolynomialRecurrence[p,x,n,r]//TraditionalForm

RSolve[{p[n,x]==(-3+x)p[n-1,x]+(-2+x)p[n-2,x],p[4,x]==(-3+x) (-2+x) (-1+x) x,p[5,x]==(-2+x) (-1+x) x (7-5 x+(x^2))},p[n,x],n]

FullSimplify[-((x (4 (((-1))^n)-(((-2+x))^n)-4 (((-1))^n) x+(((-1))^n) (x^2)))/(-2+x)),n∈Integers&&n>3]

Table[(-(((-1))^n) (-2+x)+(((-2+x))^(-1+n))) x,{n,4,19}]-p//Expand

WhiteBishop

Select[GraphData["WhiteBishop"],Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

WhiteBishop nxn

Select[GraphData["WhiteBishop"],Equal@@("WhiteBishop"/.GraphData[#,"NotationRules"])&&Head[GraphData[#,"QChromaticPolynomial"]]===Missing&]

p=DeleteCases[Table[GraphData[{"WhiteBishop",{n,n}},"QChromaticPolynomial"][x],{n,6}],(_GraphData|_Missing)[x]]//Quiet

Factor@FindPolynomialRecurrence[p,4]

Factor@FindPolynomialRecurrence[p,5]

Factor@FindPolynomialRecurrence[p,6]