Packing non-zero A-paths in group-labelled graphs

Maria Chudnovsky, Jim Geelen, Bert Gerards, Luis Goddyn, Michael Lohman, Paul Douglas Seymour

Research output: Contribution to journalArticle

42 Scopus citations

Abstract

Let G = (V,E) be an oriented graph whose edges are labelled by the elements of a group Γ and let A⊆V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Γ is not abelian, we sum the labels in their order along the path.) We are interested in the maximum number of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem. The general case also includes Mader's S-paths problem. We prove that for any positive integer k, either there are k vertex-disjoint A-paths each of non-zero weight, or there is a set of at most 2k -2 vertices that meets each of the non-zero A-paths. This result is obtained as a consequence of an exact min-max theorem.

Original languageEnglish (US)
Pages (from-to)521-532
Number of pages12
JournalCombinatorica
Volume26
Issue number5
DOIs
StatePublished - Oct 1 2006

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Packing non-zero A-paths in group-labelled graphs'. Together they form a unique fingerprint.

  • Cite this