Q-Chromatic Polynomial

The -chromatic polynomial, introduced by Birkhoff and Lewis (1946) and termed the "-chromial" by Bari (1974), is an alternate form of the chromatic polynomial  defined for graphs with chromatic number  by

Its definition is motivated by the fact that  for any graph with chromatic number , meaning dividing out the corresponding terms  from  provides a more compact representation than  since  has a smaller coefficients. When ,  is a polynomial of degree  (instead of ) for a graph with vertex count , and in the case where , it is a polynomial in  of degree  plus a term involving  (Birkhoff and Lewis 1946).

REFERENCES

Bari, R. A. "Chromatically Equivalent Graphs." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 186-200, 1974.

Birkhoff, G. D. and Lewis, D. C. "Chromatic Polynomials." Trans. Amer. Math. Soc. 60, 355-451, 1946.