Packing Seagulls
<-- Return to the list
Date: 02-03-2009
Start Time:
5:30pm
End Time: 6:30pm
Speaker: Paul Seymour, Princeton University
Location: Mudd 303
ABSTRACT
A "seagull" in a graph is an induced three-vertex path. When does a graph contain k vertex-disjoint seagulls? For general graphs this is NP-complete, by a result of Dor and Tarsi. However, because of a connection with Hadwiger's conjecture, the case of graphs with stability number two is of special interest, and henceforth we confine ourselves to such graphs. In that case we can solve the seagulls question. We give five necessary conditions, which together are sufficient.
We also solve the fractional and half-integral packing problems for seagulls, and use this (via the ellipsoid method) to give a polynomial time algorithm to test whether there exist k disjoint seagulls.
Our result implies the following, which is related to Hadwiger's conjecture, and is a strengthening and a common generalization of two theorems of Blasiak. Let G be a graph with stability number two, and with n vertices. Suppose that some clique of G has cardinality at least n/3. Then G contains Kt as a minor, where t ≥ n/2.
This is joint work with Maria Chudnovsky.