Sigma Polynomial

Author

Eric W. Weisstein
January 26, 2008

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

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

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

Definition

SigmaPolynomial[p1_,p_,chi_]:=Module[{a,p2,i,x,},
p2=FunctionExpand[Total[Table[a[i]FactorialPower[x,p-i],{i,0,p-chi}]]];
Evaluate[(Array[a,p-chi+1,0]/.ToRules[Reduce[Thread[Equal@@(CoefficientList[#,x]&/@{p1[x],p2})],Array[a,p-chi,0],Integers]]).Table[#^i,{i,0,p-chi}]]&
]

SigmaPolynomial[g_Graph]:=SigmaPolynomial[Evaluate[Function[x,ChromaticPolynomial[g,x]]],V[g],ChromaticNumber[g]]

SigmaPolynomial[Graph[{"GeneralizedQuadrangle",{2,1}}]]

Exampes

Table

GraphData[#,{"#","ChromaticPolynomial"}]&/@{"C3","C4","K4","CubicalGraph"}

{GraphData[#,"Name"],Factor@GraphData[#,"SigmaPolynomial"][x]}&/@{"S3","K5","K6","CubicalGraph","C3","C4","C5","OctahedralGraph","S4","S5","S6","K4","W5","W6"}//TableForm//TraditionalForm

Computation

(SigmaPolynomial@@GraphData["CubicalGraph",{"ChromaticPolynomial","V","ChromaticNumber"}])[x]

l=CoefficientList[%,x]

Module[{g="CubicalGraph",p,χ},
p=GraphData[g,"V"];
χ=GraphData[g,"ChromaticNumber"];
{
l.Table[FactorialPower[x,p-i],{i,0,p-χ}]//FunctionExpand//Factor,
GraphData[g,"ChromaticPolynomial"][x]
}
]

Graphs with Nonreal Roots of Sigma Polynomials

(l=Select[GraphData["SigmaPolynomial","Defined"],(Max[Im[x/.{ToRules[NRoots[GetGraphData[#,"SigmaPolynomial"][x],x]]}]]>.001&)])//Timing

TableForm[Sort[GraphData[#,{"V","#"}]&/@l],TableDepth->2]

Table[Select[GraphData[n],(Max[Im[x/.{ToRules[NRoots[GetGraphData[#,"SigmaPolynomial"][x],x]]}]]>.001&)],{n,6}]

Select[Range[Length[Graphs[7]]],(Max[Im[x/.{ToRules[NRoots[GetGraphData[RecognizeGraph[Graph[{7,#}]],"SigmaPolynomial"][x],x]]}]]>.001&)]//Quiet

Select[Range[Length[Graphs[8]]],(Max[Im[x/.{ToRules[NRoots[GetGraphData[RecognizeGraph[Graph[{8,#}]],"SigmaPolynomial"][x],x]]}]]>.001&)]//Quiet