Thursday, July 26, 2018 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Title: Acyclic Colouring of Graphs on Surfaces
| Speaker: | Shayla Redlin |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: An
acyclic
k-colouring
of
a
graph
G
is
a
proper
k-colouring
of
G
with
no
bichromatic
cycles.
A
graph
G
is
critical
for
acyclic
k-colouring
if
G
is
not
acyclically
k-colourable,
but
all
proper
subgraphs
are.
We
prove
that,
for
k
12
and
for
each
surface
S,
there
are
nitely
many
graphs
embeddable
on
S
that
are
critical
for
acyclic
k-colouring.
In
this
talk,
I
will
discuss
the
history
of
the
problem
and
outline
the
proof.