Online Talk: Louis Esperet

Tuesday, March 1, 11am ET (4pm GMT, 5am Wed NZDT)
Louis Esperet, G-SCOP Laboratory (CNRS, Grenoble)
Packing and covering balls in planar graphs

 
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.

Online Talk: Chun-Hung Liu

Tuesday, Feb 15, 4pm ET (9pm GMT, 10am Wed NZDT)
Chun-Hung Liu, Texas A&M University
Homomorphism counts in robustly sparse graphs

 
Abstract:
For a fixed graph $H$ and for arbitrarily large host graphs $G$, the number
of homomorphisms from $H$ to $G$ and the number of subgraphs isomorphic to $H$
contained in $G$ have been extensively studied when the host graphs are
allowed to be dense. This talk addresses the case when the host graphs
are robustly sparse. We determine, up to a constant multiplicative
error, the maximum number of subgraphs isomorphic to $H$ contained in an
$n$-vertex graph in any fixed hereditary graph class with bounded
expansion. This result solves a number of open questions and can be
generalized to counting the number of homomorphisms.

Online Talk: Sophie Spirkl and James Davies

Tuesday, Feb 8, 3pm ET (8pm GMT, 9am Wed NZDT)
Sophie Spirkl and James Davies, University of Waterloo
Two counterexamples related to chi-boundedness

 
Abstract:
Sophie Spirkl: I will present a counterexample to the following well-known conjecture: for every $k$, $r$, every graph $G$ with clique number at most $k$ and sufficiently large chromatic number contains a triangle-free induced subgraph with chromatic number at least $r$.
Joint work with Alvaro Carbonero, Patrick Hompe, and Benjamin Moore.

James Davies: We construct hereditary classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded.
Joint work with Marcin Briański and Bartosz Walczak.