TOPICS
Search

Sigma Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Let a simple graph G have n vertices, chromatic polynomial P(x), and chromatic number chi. Then P(G) can be written as

P(G)=sum_(i=0)^ha_i·(x)_(p-i),

where h=n-chi and (x)_k is a falling factorial, and the polynomial

sigma(G)=sum_(i=0)^ha_ix^(h-i)

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 Gsigma(G)
claw graph S_4x^2+3x+1
complete graph K_61
cubical graphx^6+18x^5+92x^4+146x^3+80x^2+16x+1
cycle graph C_55x^2+5x+1
octahedral graph(x+1)^3
path graph P_3x+1
pentatope graph K_51
square graph C_4(x+1)^2
star graph S_5x^3+7x^2+6x+1
star graph S_6x^4+15x^3+25x^2+10x+1
tetrahedral graph K_41
triangle graph C_31
wheel graph W_5(x+1)^2
wheel graph W_65x^2+5x+1

See also

Chromatic Polynomial, Royle Graphs

Explore with Wolfram|Alpha

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 Polynomial

Cite this as:

Weisstein, Eric W. "Sigma Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SigmaPolynomial.html

Subject classifications