search

#### Speaker - Carole Muller

Packing and covering balls in graphs excluding a minor Wed, Mar 11, 2020 12:30 CET

###### Speakers:Carole Muller

Given a graph $G$, the ball centered at vertex $v$ of radius $r$ is the set containing all vertices at distance at most $r$ from $v$. We prove that for every integer $t\ge 1$ there exists a constant $c_t$ such that for every $K_t$-minor-free graph $G$, and every set $S$ of balls in $G$, the minimum size of a set of vertices of $G$ intersecting all the balls of $S$ is at most $c_t$ times the maximum number of vertex-disjoint balls in $S$.

Excluded minors for isometric embeddings of graphs in $\ell_\infty^k$-spaces Wed, May 31, 2017 12:30 CEST