A quick proof of Seymour's theorem on t-joins (Q1089008)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4002136
Language Label Description Also known as
default for all languages
No label defined
    English
    A quick proof of Seymour's theorem on t-joins
    scientific article; zbMATH DE number 4002136

      Statements

      A quick proof of Seymour's theorem on t-joins (English)
      0 references
      0 references
      1987
      0 references
      Let G be a graph and t: V(G)\(\to \{0,1\}\) where t(V(G)) is even. (If \(X\subseteq V(G)\), then \(t(X):=\Sigma \{t(x):\) \(x\not\in X\}.)\) A t-join is a set \(F\subseteq E(G)\) with \(d_ F(x)\equiv t(x)\) (mod 2), \(\forall x\in V(G)\). \((d_ F(x)\) denotes the number of edges of F incident with x, where loops count twice.) t-joins contain Chinese postman tours, matchings and minimum weight paths as a special case. If \(X\subseteq V(G)\), let \(\delta (X)=\{xy\in E(G):\) \(y\not\in X\), \(x\in X\}\). If t(X)\(\equiv 1(mod 2)\), then \(\delta\) (X) is called a t-cut. t-cuts contain plane multicommodity flows as a special case. \textit{P. O. Seymour} [Proc. Lond. Math. Soc., III. Ser. 42, 178-192 (1981; Zbl 0447.90026)] proved that if G is bipartite then \(\tau (G,t)=\nu (G,t)\). The author gives a short proof of this.
      0 references
      t-join
      0 references
      Chinese postman tours
      0 references
      matchings
      0 references
      minimum weight paths
      0 references
      t-cuts
      0 references
      plane multicommodity flows
      0 references

      Identifiers