Location: ** HILL 705**

Date & time: Monday, 02 October 2017 at 2:00PM - 3:00PM

: | Abstract: For a family F of graphs, the packing number p of a graph G for F is the maximum size of a collection of pairwise disjoint subgraphs of G where each isomorphic to a member of F; the covering number c of G for F is the minimum size of a subset of vertices of G intersecting all subgraphs of G isomorphic to members of F. We say F has the Erdos-Posa property if there exists a function f such that c is at most f(p) for every graph G. Robertson and Seymour proved that if F is the set of H minors for some graph H, then F has the Erdos-Posa property if and only if H is planar. In this talk I will provide a complete but complicated characterization for the graphs H such that the set of H subdivisions has the Erdos-Posa property, and show that it is NP-hard to decide whether the input graph H has this property, so that the complication of the characterization is unlikely to be avoidable. This is joint work with Luke Postle and Paul Wollan and answers a question of Robertson and Seymour. Then I will discuss how to simplify the characterization by relaxing the conditions for having the Erdos-Posa property. In particular, I will show that for every graph H, the set of H subdivisions always has the Erdos-Posa property if we allow the packing to be half-integral. This statement easily implies a conjecture of Thomas. |
---|

Department of Mathematics
Rutgers University Hill Center - Busch Campus 110 Frelinghuysen Road Piscataway, NJ 08854-8019, USA Phone: +1.848.445.2390 Fax: +1.732.445.5530 |