Packing seagulls |
| |
Authors: | Maria Chudnovsky Paul Seymour |
| |
Affiliation: | 1. Columbia University, New York, NY, 10027, USA 2. Princeton University, Princeton, NJ, 08540, USA
|
| |
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. 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 - |V (G)|≥3k
- G is k-connected
- for every clique C of G, if D denotes the set of vertices in V (G)C that have both a neighbour and a non-neighbour in C then |D|+|V (G)C|≥2k, 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|