Paper Info
Title
Packing seagulls.
Abstract
A 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.
Year
DOI
Venue
2012
10.1007/s00493-012-2594-2
Combinatorica
DocType
Volume
Issue
Journal
32
3
ISSN
Citations 
PageRank 
1439-6912
0
0.34
References 
Authors
2
2
Name
Order
Citations
PageRank
Maria Chudnovsky139046.13
Paul D. Seymour22786314.49