Title: Coloring Graphs on Surfaces
| Speaker: | Luke Postle |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
A
coloring
of
a
graph
is
an
assignment
of
colors
to
the
vertices
such
that
no
two
adjacent
vertices
receive
the
same
color.
Coloring
graphs
embedded
on
surfaces
(e.g.
the
plane,
torus,
klein
bottle,
etc.)
has
been
a
much
studied
area
of
research
in
graph
theory
dating
from
the
proposal
of
the
Four
Color
Conjecture
in
1852.
In
this
talk,
we
examine
a
number
of
recent
questions
that
have
been
raised
about
coloring
graphs
on
surfaces
such
as:
Can
we
precolor
some
of
the
vertices
and
still
get
a
coloring?
Can
we
allow
some
of
the
edges
to
cross
and
still
get
a
coloring?
If
there
is
a
coloring,
can
we
get
exponentially
many
different
colorings?
Can
we
decide
in
polynomial
time
if
there
is
a
coloring
with
a
small
number
of
colors?