A refinement of the Frank-Sebö-Tardos theorem and its applications. (English. Russian original) Zbl 0835.05054
Korshunov, A. D. (ed.): Discrete analysis and operations research. Mathematics and its Applications 355, 109-123 (1996); translation from Sib. Zh. Issled. Oper. 1, No. 3, 3-19 (1994).
Let \(\tau (G,T)\) be the minimum size of \(T\)-joins and \(\nu (G,T)\) the maximum number of pairwise disjoint \(T\)-cuts in \(G\). It is proved that there is a special set of \(\nu (G,T)\) pairwise disjoint \(T\)-cuts if \(G\) is a bipartite graph (in this case \(\tau (G,T) = \nu (G,T))\), and this gives some new upper bounds for \(\tau (G,T)\).
Reviewer: M.Knor (Bratislava)
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C20 | Directed graphs (digraphs), tournaments |
