Loading Events

« All Events

  • This event has passed.
:

Gwenaël Joret, Packing and covering balls in graphs excluding a minor

Wednesday, August 19, 2020 @ 4:30 PM - 5:30 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

Gwenaël Joret
Computer Science Department, Université Libre de Bruxelles
https://di.ulb.ac.be/algo/gjoret/

In 2007, Chepoi, Estellon, and Vaxès conjectured that there exists a universal constant $c>0$ such that the following holds for every positive integers $r$ and $k$, and every planar graph $G$: Either $G$ contains $k$ vertex-disjoint balls of radius $r$, or there is a subset of vertices of size at most $c k$ meeting all balls of radius $r$ in $G$. The key aspect of this conjecture is that the constant $c$ does not depend on the radius $r$ of the balls. If we were to allow this dependency, then the statement is known to hold, and in fact it is true in the more general setting of graph classes with bounded expansion (as proved by Dvořák).

In this talk I will present a proof of this conjecture. The result we prove is a bit more general: (1) The conjecture holds for every proper minor-closed class of graphs (with the constant $c$ depending on the class), and (2) we can even focus on any set of balls in the graph we like, there is nothing special about taking all balls of a given radius. In other words, we show that for every proper minor-closed class $C$ of graphs, there exists a constant $c>0$ such that for every graph $G$ in $C$, every set $S$ of balls in $G$, and every positive integer $k$, either there are $k$ vertex-disjoint balls in $S$, or there is a subset of vertices of $G$ of size at most $c k$ meeting all balls in $S$.

Joint work with Nicolas Bousquet, Wouter Cames van Batenburg, Louis
Esperet, William Lochet, Carole Muller, and François Pirot.

Details

Date:
Wednesday, August 19, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.