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:
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)
“The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.”
—Samuel Taylor Coleridge (1772–1834)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)