Sigma Polynomial
Let a simple graph G have n vertices, chromatic polynomial P(x), and chromatic number chi. Then P(G) can be written as
where h=n-chi and (x)_k is a falling factorial, and the polynomial
is known as the sigma-polynomial (Frucht and Giudici 1983; Li et al. 1987; Read and Wilson 1998, p. 265).
sigma-polynomials for a number of simple graphs are summarized in the following table.
graph G sigma(G)
claw
graph S_4 x^2+3x+1
complete graph K_6 1
cubical graph x^6+18x^5+92x^4+146x^3+80x^2+16x+1
cycle graph C_5 5x^2+5x+1
octahedral
graph (x+1)^3
path
graph P_3 x+1
pentatope graph K_5 1
square graph C_4 (x+1)^2
star
graph S_5 x^3+7x^2+6x+1
star graph S_6 x^4+15x^3+25x^2+10x+1
tetrahedral graph K_4 1
triangle graph C_3 1
wheel graph W_5 (x+1)^2
wheel
graph W_6 5x^2+5x+1
See also
Chromatic Polynomial, Royle GraphsExplore with Wolfram|Alpha
WolframAlpha
More things to try:
References
Frucht, R. W. and Giudici, R. E. "Some Chromatically Unique Graphs with Seven Points." Ars Combin. A 16, 161-172, 1983.Korfhage, R. R. "sigma-Polynomials and Graph Coloring." J. Combin. Th. Ser. B 24, 137-153, 1978.Li, N.-Z.; Whitehead, E. G. Jr.; and Xu, S.-J. "Classification of Chromatically Unique Graphs Having Quadratic sigma-Polynomials." J. Graph Th. 11, 169-176, 1987.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 265, 1998.Referenced on Wolfram|Alpha
Sigma PolynomialCite this as:
Weisstein, Eric W. "Sigma Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SigmaPolynomial.html