Definition
The chromatic polynomial of a graph counts the number of its proper vertex colorings. It is commonly denoted, or, and sometimes in the form, where it is understood that for fixed the function is a polynomial in, the number of colors.
For example, the path graph on 3 vertices cannot be colored at all with 0 or 1 colors. With 2 colors, it can be colored in 2 ways. With 3 colors, it can be colored in 12 ways.
| Available colors | 0 | 1 | 2 | 3 |
| Number of colorings | 0 | 0 | 2 | 12 |
The chromatic polynomial is defined as the unique interpolating polynomial of degree through the points for, where is the number of vertices in . For the example graph, and indeed .
The chromatic polynomial includes at least as much information about the colorability of as does the chromatic number. Indeed, the chromatic number is the smallest positive integer that is not a root of the chromatic polynomial,
Read more about this topic: Chromatic Polynomial
Famous quotes containing the word definition:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)