Tuesday, March 1, 2022 11:00 am
-
11:00 am
EST (GMT -05:00)
Title: Packing and covering balls in planar graphs
| Speaker: | Louis Esperet |
| Affiliation: | G-SCOP Laboratory |
| Zoom: | Join via http://matroidunion.org/?page_id=2477 or please email Shayla Redlin |
Abstract:
The
set
of
all
vertices
at
distance
at
most
r
from
a
vertex
v
in
a
graph
G
is
called
an
r-ball.
We
prove
that
the
minimum
number
of
vertices
hitting
all
r-balls
in
a
planar
graph
G
is
at
most
a
constant
(independent
of
r)
times
the
maximum
number
of
vertex-disjoint
r-balls
in
G.
This
was
conjectured
by
Estellon,
Chepoi
and
Vaxès
in
2007.
Our
result
holds
more
generally
for
any
proper
minor-closed
class,
and
for
systems
of
balls
of
arbitrary
(and
possibly
distinct)
radii.
Joint
work
with
N.
Bousquet,
W.
Cames
van
Batenburg,
G.
Joret,
W.
Lochet,
C.
Muller,
and
F.
Pirot.