9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

Optimal Erdös-Pósa property for pumpkins

Presented by Dr. Ignasi SAU
Type: Oral presentation
Track: Graph Theory

Content

A class of graphs F satisfies the Erdös-Pósa property if there exists a function f such that, for every integer k and every graph G, either G contains k vertex-disjoint subgraphs each isomorphic to a graph in F, or there is a set S ⊆ V (G) of at most f(k) vertices such that G \ S has no subgraph in F. Erdös and Pósa [1965] proved that the set of all cycles satisfies this property with f(k)=O(k·log(k)). Given a connected graph H, let M(H) be the class of graphs that can be contracted to H. Robertson and Seymour [1986] proved that M(H) satisfies the Erdös-Pósa property if and only if H is planar. The function f derived from the proof of this result is super-exponential, and this has been the best general upper bound for almost 30 years. Some months ago, Chekuri and Chuzhoy [2013] proved that f(k)=O(k·polylog(k)). On the other hand, it is known that for any planar graph H containing a cycle, it holds that f(k)=Ω(k·log(k)), so it is interesting to find particular cases of planar graphs H for which this lower bound is attained. In this talk we present how to obtain an asymptotically optimal function f(k)=O(k·log(k)) for the c-pumpkin, which is the graph with two vertices linked by c>0 parallel edges, and can be seen as a natural generalization of a cycle. This is joint work with Samuel Fiorini and Gwenaël Joret.

Place

Location: Koper, Slovenia

Primary authors

More