Packing odd paths

A. Schrijver, P. D. Seymour

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Let s, t be vertices of a graph G, and let each edge e have a “capacity” c(e) ∈ R+. We prove a conjecture of Cook and Sebo(combining double acute accent) that for every k ∈ R+, the following two statements are equivalent: (i) there is a “fractional packing” of value k of the odd length s - t paths, so that no edge is used more than its capacity; (ii) for every subgraph H of G with s, t ∈ V(H) in which there is no odd s - t path, [formula] ∑ (c(e): e ∈ E(G) - E(H), and e is incident with v ≥ 2k.

Original languageEnglish (US)
Pages (from-to)280-288
Number of pages9
JournalJournal of Combinatorial Theory, Series B
Volume62
Issue number2
DOIs
StatePublished - Nov 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Packing odd paths'. Together they form a unique fingerprint.

Cite this