Sigma Polynomial

Let a simple graph  have  vertices, chromatic polynomial , and chromatic number . Then  can be written as

where  and  is a falling factorial, and the polynomial

is known as the -polynomial (Frucht and Giudici 1983; Li et al. 1987; Read and Wilson 1998, p. 265).

-polynomials for a number of simple graphs are summarized in the following table.

graph
claw graph
complete graph	1
cubical graph
cycle graph
octahedral graph
path graph
pentatope graph	1
square graph
star graph
star graph
tetrahedral graph	1
triangle graph	1
wheel graph
wheel graph

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. "-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 -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.