zbMATH — the first resource for mathematics

Vertex set partitions preserving conservativeness. (English) Zbl 1027.05078
Summary: Let \(G\) be an undirected graph and \({\mathcal P}= \{X_1,\dots, X_n\}\) be a partition of \(V(G)\). Denote by \(G/{\mathcal P}\) the graph which has vertex set \(\{X_1,\dots, X_n\}\), edge set \(E\), and is obtained from \(G\) by identifying vertices in each class \(X_i\) of the partition \({\mathcal P}\). Given a conservative graph \((G,{\mathbf w})\), we study vertex set partitions preserving conservativeness, i.e., those for which \((G/{\mathcal P},{\mathbf w})\) is also a conservative graph. We characterize the conservative graphs \((G/{\mathcal P},{\mathbf w})\), where \({\mathcal P}\) is a terminal partition of \(V(G)\) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs of A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997), a theorem of E. Korach (1994), a theorem of E. Korach and M. Penn (1992), and a theorem of A. V. Kostochka (1994).

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
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
[2] Frank, A., A survey on T-joins, T-cuts, and conservative weightings, Combinatorics, paul erdős is eighty, (1996), p. 213-252 · Zbl 0846.05062
[3] Gerards, A.M.H., On shortest T-joins and packing T-cuts, J. combin. theory ser. B, 55, 73-82, (1992) · Zbl 0810.05056
[4] Korach, E., Two-trees optimal T-join and integral packing of T-cuts, J. combin. theory ser. B, 62, 1-10, (1994) · Zbl 0807.05062
[5] Korach, E.; Penn, M., Tight integral duality gap in the Chinese postman problem, Math. programming, 55, 183-191, (1992) · Zbl 0767.90088
[6] Kostochka, A.V., A refinement of the frank – sebő-tardos theorem and its applications, (), 109-113 · Zbl 0835.05054
[7] Kostochka, A.V.; Tulai, N., On the length of the Chinese postman tour in regular graphs, (), 125-141
[8] Lovász, L.; Plummer, M.D., Matching theory, (1986), Kiadó Budapest · Zbl 0618.05001
[9] Sebő, A., The factors of graphs: structure and algorithms, (1987), Eötvös University
[10] Sebö, A., Undirected distances and the postman structure of graphs, J. combin. theory ser. B, 49, 10-39, (1990) · Zbl 0638.05032
[11] Seymour, P.D., The matroids with the MAX-flow MIN-cut property, J. combin. theory ser. B, 23, 189-222, (1977) · Zbl 0375.05022
[12] Seymour, P.D., On odd cuts and plane multicommodity flows, Proc. London math. soc. (3), 42, 178-192, (1981) · Zbl 0447.90026
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.