A quick proof of Seymour's theorem on t-joins
type: Item
instance of: scholarly article
title: A quick proof of Seymour's theorem on t-joins
zbMATH Open document ID: 0618.05040
DOI: 10.1016/0012-365X(87)90246-9
author: András Sebö
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4002136
zbMATH Keywords: t-join
zbMATH Keywords: Chinese postman tours
zbMATH Keywords: matchings
zbMATH Keywords: minimum weight paths
zbMATH Keywords: t-cuts
zbMATH Keywords: plane multicommodity flows
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Matching, Euler tours and the Chinese postman
cites work: Covering directed and odd cuts
cites work: On two minimax theorems in graph
cites work: Q3880849
cites work: Q5519709
cites work: The scholar as craftsman: Derek de Solla Price and the reconstruction of a medieval instrument
cites work: On Odd Cuts and Plane Multicommodity Flows
full work available at URL: 0012-365x(87)90246-9
OpenAlex ID: W1975569664
description: scientific article; zbMATH DE number 4002136