• Monday 9:00 -- Chun-Hung Liu

Title: Weak coarse Menger property of minor-closed families

        Abstract:

A graph or a graph class has the weak coarse Menger property if there exist functions f and g such that for any subsets X and Y of vertices and integers k and r, either there exist k paths from X to Y with pairwise at distance at least r, or there exists a union of f (k, r) balls of radius g(k, r) hitting all paths from X to Y . Nguyen, Scott and Seymour proved that the class of all graphs does not have the weak coarse Menger property and asked whether minor-closed families have it. We answer this question affirmatively in a stronger form by showing that rooted fat K_2-minors have the coarse Erdős-Pósa property in minor-closed families, which also implies that A-paths have the coarse Erdős-Pósa property in minor-closed families. What we actually proved is that it holds for every length space quasi-isometric to a finite or locally finite infinite graph with an excluded minor, implying that the aforementioned results hold for complete Riemannian surfaces of finite Euler genus, metric graphs with an excluded minor, and string graphs.

• Tuesday 9:00 -- Youngho Yoo

        Title: Erdős-Pósa property in group-labelled graphs

        Abstract:

In a group-labelled graph, the edges are labelled by elements of a fixed group and the “length” of a walk is determined by applying the group operation to the labels of its edges in the order they appear on the walk. This framework encapsulates many natural length constraints and, in recent years, general structure theorems on group-labelled graphs have been developed to obtain Erdős-Pósa results on paths and cycles with length constraints. In this talk, I will discuss these results and techniques and present some open problems.

•  Wednesday 9:00 -- James Davies

 Title: The coarse Erdős-Pósa theorem

Abstract:

We prove the coarse Erdős-Pósa conjecture of Georgakopoulos and Papasoglu. To be more precise, for every graph G, if n · K_3 is not a q-fat minor of G, then there is a set S of at most f(n) vertices of G such that the ball of radius O(q) around S meets all q-fat K_3 minors of G.
Joint work with Sandra Albrechtsen, Marthe Bonamy, and Romain Bourneuf.

•     Thursday 9:00 --  Sang-Il Oum
  
  Title: The Erd\H{o}s-P\'{o}sa property for circle graphs as vertex-minors

Abstract

The vertex-minors of a graph G are the graphs that can be obtained from G by deleting vertices and by performing certain "local moves" called local complementations; locally complementing at a vertex v replaces the induced subgraph on the neighborhood of v by its complement. Circle graphs are the intersection graphs of the chords of a circle.

We prove that for any circle graph H with at least one edge and for any positive integer k, there exists an integer t=t(k,H) so that every graph G either has a vertex-minor isomorphic to the disjoint union of k copies of H, or has a t-perturbation with no vertex-minor isomorphic to H. Using the same techniques, we also prove that for any planar multigraph H, every binary matroid either has a minor isomorphic to the cycle matroid of kH, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of H.

This is joint work with Rutger Campbell, J. Pascal Gollin, Meike Hatzel, Rose McCarty, and Sebastian Wiederrecht.