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:
“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)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)