Packing seagulls

Research output: Contribution to journalArticle

3 Scopus citations

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 • {pipe}V (G){pipe} ≥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 {pipe}D{pipe}+{pipe}V (G)/C{pipe}≥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.

Original languageEnglish (US)
Pages (from-to)251-282
Number of pages32
JournalCombinatorica
Volume32
Issue number3
DOIs
StatePublished - Apr 1 2012

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Packing seagulls'. Together they form a unique fingerprint.

  • Cite this