Vertex
coloring
When
used
without
any
qualification
a
coloring
of
a
graph
is
almost
always
a
proper
vertex
coloring
namely
a
labelling
of
the
graphs
vertices
with
colors
such
that
no
two
vertices
sharing
the
same
edge
have
the
same
color
Since
a
vertex
with
a
loop
could
never
be
properly
colored
it
is
understood
that
graphs
in
this
context
are
loopless
The
terminology
of
using
colors
for
vertex
labels
goes
back
to
map
coloring
Labels
like
red
and
blue
are
only
used
when
the
number
of
colors
is
small
and
normally
it
is
understood
that
the
labels
are
drawn
from
the
integers
123
A
coloring
using
at
most
k
colors
is
called
a
proper
kcoloring
The
smallest
number
of
colors
needed
to
color
a
graph
G
is
called
its
chromatic
number
G
A
graph
that
can
be
assigned
a
proper
kcoloring
is
kcolorable
and
it
is
kchromatic
if
its
chromatic
number
is
exactly
k
A
subset
of
vertices
assigned
to
the
same
color
is
called
a
color
class
every
such
class
forms
an
independent
set
Thus
a
kcoloring
is
the
same
as
a
partition
of
the
vertex
set
into
k
independent
sets
and
the
terms
kpartite
and
kcolorable
have
the
same
meaning
editChromatic
polynomial
All
nonisomorphic
graphs
on
3
vertices
and
their
chromatic
polynomials
The
empty
graph
E3
red
admits
a
1coloring
the
others
admit
no
such
colorings
The
green
graph
admits
12
colorings
with
3
colors
Main
article
Chromatic
polynomial
The
chromatic
polynomial
counts
the
number
of
ways
a
graph
can
be
colored
using
no
more
than
a
given
number
of
colors
For
example
using
three
colors
the
graph
in
the
image
to
the
right
can
be
colored
in
12
ways
With
only
two
colors
it
cannot
be
colored
at
all
With
four
colors
it
can
be
colored
in
24
412
72
ways
using
all
four
colors
there
are
4
24
valid
colorings
every
assignment
of
four
colors
to
any
4vertex
graph
is
a
proper
coloring
and
for
every
choice
of
three
of
the
four
colors
there
are
12
valid
3colorings
So
for
the
graph
in
the
example
a
table
of
the
number
of
valid
colorings
would
start
like
th