WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

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.
Wolfram Cloud

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


I understand and wish to continue anyway »

You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.