Chromatic Polynomials

type of graph

Cycle

Complete

Wheel

Star

K-ary Tree

number of vertices n

4

5

6

7

8

4

(x-1)

x

A coloring of the vertices of a graph

G

is an assignment of

x

or fewer colors to the vertices of

G

so that no two adjacent vertices get the same color. The chromatic polynomial

CP(G)(x)

of

G

is a polynomial giving the number of distinct colorings of

G

. If

G

has

n

vertices,

CP(G)(x)

is monic (the coefficient of the highest power equals 1) of degree

n

with integer coefficients alternating in sign and beginning

1,-e,…

, where

e

is the number of edges of

G

. Moreover,

CP(G)(1)=0

unless

n=1

and

CP(G)(0)=0

. This Demonstration shows the chromatic polynomial corresponding to a selection of members of prominent families of graphs.

External Links

Graph (Wolfram Documentation Center)

ChromaticPolynomial (Wolfram Documentation Center)

Graph (Wolfram MathWorld)

Chromatic Polynomial (Wolfram MathWorld)

Permanent Citation

Jaime Rangel-Mondragon

"Chromatic Polynomials"
http://demonstrations.wolfram.com/ChromaticPolynomials/
Wolfram Demonstrations Project
Published: August 16, 2011