Tuesday, April 5, 2022 3:00 pm
-
3:00 pm
EDT (GMT -04:00)
Title: A local version of Hadwiger’s Conjecture
| Speaker: | Lise Turner |
| Affiliation: | University of Waterloo |
| Zoom: | http://matroidunion.org/?page_id=2477 or contact Shayla Redlin |
Abstract:
In
1943,
Hadwiger
famously
conjectured
that
graphs
with
no
$K_t$
minors
are
$t-1$
colourable.
There
has
also
been
significant
interest
in
several
variants
of
the
problem,
such
as
list
colouring
or
only
forbidding
certain
classes
of
minors.
We
propose
a
local
version
where
all
balls
of
radius
$O(\log
v(G))$
must
be
$K_t$-minor
free
but
the
graph
as
a
whole
may
not
be.
We
prove
list
colouring
results
for
these
graphs
equivalent
to
the
best
known
results
for
$K_t$-minor
free
graphs
for
$t\leq
5$
and
large
$t$.
In
the
process,
we
provide
some
efficient
distributed
algorithms
for
finding
such
colourings.
Joint
work
with
Benjamin
Moore
and
Luke
Postle.