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:
“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)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)