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

From MaRDI portal
scientific article
Language Label Description Also known as
English
A quick proof of Seymour's theorem on t-joins
scientific article

    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