# Packing seagulls

## Author(s): Chudnovsky, Maria; Seymour, Paul D.

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1x372
DC FieldValueLanguage
dc.contributor.authorChudnovsky, Maria-
dc.contributor.authorSeymour, Paul D.-
dc.date.accessioned2018-07-20T15:06:46Z-
dc.date.available2018-07-20T15:06:46Z-
dc.date.issued2012-04en_US
dc.identifier.citationChudnovsky, Maria, Seymour, Paul. (2012). Packing seagulls. COMBINATORICA, 32 (251 - 282. doi:10.1007/s00493-012-2594-2en_US
dc.identifier.issn0209-9683-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1x372-
dc.description.abstractA seagull in a graph is an induced three-vertex path. When does a graph G have k pairwise vertex-disjoint seagulls? This is NP-complete in general, but for graphs with no stable set of size three we give a complete solution. This case is of special interest because of a connection with Hadwiger’s conjecture which was the motivation for this research; and we deduce a unification and strengthening of two theorems of Blasiak [2] concerned with Hadwiger’s conjecture. Our main result is that a graph G (different from the five-wheel) with no three-vertex stable set contains k disjoint seagulls if and only if vertical bar V vertical bar(G) >= 3K G is k-connected for every clique C of G, if D denotes the set of vertices in V (G)\textbackslashC that have both a neighbour and a non-neighbour in C then |D|+|V (G)\textbackslashC|a parts per thousand yen2k, and the complement graph of G has a matching with k edges. We also address the analogous fractional and half-integral packing questions, and give a polynomial time algorithm to test whether there are k disjoint seagulls.en_US
dc.format.extent251 - 282en_US
dc.language.isoen_USen_US
dc.relation.ispartofCOMBINATORICAen_US
dc.rightsAuthor's manuscripten_US
dc.titlePacking seagullsen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1007/s00493-012-2594-2-
dc.date.eissued2012-06-07en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat