zbMATH — the first resource for mathematics

An excluded minor characterization of Seymour graphs. (English) Zbl 1298.05295
Günlük, Oktay (ed.) et al., Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15–17, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20806-5/pbk). Lecture Notes in Computer Science 6655, 1-13 (2011).
Summary: A graph \(G\) is said to be a Seymour graph if for any edge set \(F\) there exist \(|F|\) pairwise disjoint cuts each containing exactly one element of \(F\), provided for every circuit \(C\) of \(G\) the necessary condition \(|C \cap F| \leq |C \setminus F|\) is satisfied. Seymour graphs behave well with respect to some integer programs including multiflow problems, or more generally odd cut packings, and are closely related to matching theory.
A first coNP characterization of Seymour graphs has been shown by A. A. Ageev et al. [J. Graph Theory 24, No. 4, 357–364 (1997; Zbl 0869.05051)], the recognition problem has been solved in a particular case by A. M. H. Gerards [J. Comb. Theory, Ser. B 55, No. 1, 73–82 (1992; Zbl 0810.05056)], and the related cut packing problem has been solved in the corresponding special cases. In this article we show a new, minor-producing operation that keeps this property, and prove excluded minor characterizations of Seymour graphs: the operation is the contraction of full stars, or of odd circuits. This sharpens the previous results, providing at the same time a simpler and self-contained algorithmic proof of the existing characterizations as well, still using methods of matching theory and its generalizations.
For the entire collection see [Zbl 1216.90002].
05C83 Graph minors
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Ageev, A.A., Kostochka, A.V., Szigeti, Z.: A characterization of Seymour graphs. J. Graph Theory 24, 357–364 (1997) · Zbl 0869.05051 · doi:10.1002/(SICI)1097-0118(199704)24:4<357::AID-JGT8>3.0.CO;2-N
[2] Gerards, A.M.H.: On shortest T-joins and packing T-cuts. J. Combin. Theory Ser. B 5, 73–82 (1992) · Zbl 0810.05056 · doi:10.1016/0095-8956(92)90032-S
[3] Lovász, L.: 2-matchings and 2-covers of hypergraphs. Acta. Math. Sci. Hungar. 26, 433–444 (1975) · Zbl 0339.05123 · doi:10.1007/BF01902352
[4] Lovász, L., Plummer, M.D.: Matching Theory, Akadémiai Kiadó, Budapest (1986)
[5] Middendorf, M., Pfeiffer, F.: On the complexity of the edge-disjoint paths problem. Combinatorica 13(1), 97–108 (1993) · Zbl 0770.68072 · doi:10.1007/BF01202792
[6] Guan, M.G.: Graphic programming using odd and even points. Chinese Mathematics 1, 273–277 (1962) · Zbl 0143.41904
[7] Sebö, A.: o, Undirected distances and the postman structure of graphs. J. Combin. Theory Ser. B 49, 10–39 (1990) · Zbl 0638.05032 · doi:10.1016/0095-8956(90)90062-5
[8] Seymour, P.D.: The matroids with the max-flow min-cut property. J. Combin. Theory Ser. B 23, 189–222 (1977) · Zbl 0375.05022 · doi:10.1016/0095-8956(77)90031-4
[9] Seymour, P.D.: On odd cuts and plane multicommodity flows. Proc. London Math. Soc. Ser. 42(3), 178–192 (1981) · Zbl 0447.90026 · doi:10.1112/plms/s3-42.1.178
[10] Szigeti, Z.: On Seymour graphs, Technical Report No. 93803, Institute for Operations Research, Universität Bonn (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.