Title: How many colors can be saved?
| Speaker: | Luke Postle |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
In
1998,
Reed
proved
that
the
chromatic
number
of
a
graph
is
bounded
away
from
its
maximum
degree
and
towards
its
clique
number.
Alternatively,
one
can
save
a
number
of
colors
proportional
to
the
difference
between
the
clique
number
and
maximum
degree.
Here
we
discuss
various
generalizations
of
this
result.
First,
we
examine
extensions
of
Reed's
result
for
list-coloring
and
for
a
generalization
of
list
coloring
called
correspondence
coloring,
first
introduced
by
Dvorak.
We
apply
these
generalizations
to
progress
on
a
conjecture
of
Erdos
and
Nesteril
that
the
strong
chromatic
index
of
a
graph
is
at
most
1.25
times
the
maximum
degree
squared.
Second,
we
examine
generalizations
of
Reed's
result
where
the
list,
sizes
degree
sizes
and
clique
numbers
are
allowed
to
vary
locally
over
the
vertices.
Third,
we
apply
these
local
list
versions
to
show
that
the
chromatic
number
of
a
graph
is
bounded
away
from
its
maximum
average
degree
and
toward
its
clique
number.
Equivalently,
we
give
a
multiplicative
improvement
in
the
ratio
of
edges
to
vertices
in
a
k-critical
graph
without
a
clique
of
size
pk
for
all
p
<
0.99.
Joint work with Marthe Bonamy, Da Qi Chen and Thomas Perrett.