Friday, February 8, 2019 1:00 pm
-
1:00 pm
EST (GMT -05:00)
Title:‘Coloring 3-colorable graphs with o(n^1⁄5) colors’ by Kawarabayashi and Thorup
| Speaker: | Tom Kelly |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
Much
attention
has
been
devoted
to
nding
polynomial
time
algorithms
for
coloring
three-
colorable
graphs
with
the
fewest
possible
colors.
Kawarabayashi
and
Thorup
recently
found
such
an
algorithm
using
o(n1=5)
colors,
where
n
is
the
number
of
vertices.
Their
approach
uses
a
new
combinatorial
recursion
combined
with
semi-denite
programming.
In
this
talk,
I
will
present
the
combinatorial
aspects
of
their
result.