To describe graph-coloring in rigorous mathematical terms, let the set
denote the nodes of an undirected graph
and let
denote the edges in
, or
. Graph edges are tuples
, where
and
. The two nodes are defined to be neighbors
if the tuple
. Given a graph
, we define
a coloring of
to be an assignment of colors to the
nodes
of
such that no two adjacent nodes are
given the same color. This can be restated as a coloring of
is a mapping
such that
. The color of node i is
and
. The minimum possible value for
is known as the chromatic number of
,
which we denote as
[32].