TY - JOUR
T1 - Vertex set partitions preserving conservativeness
AU - Ageev, A. A.
AU - Kostochka, A. V.
N1 - Funding Information:
2This author finished his part of the work during a stay at SFB343 ‘‘Diskrete Strukturen in der Mathematik’’ of Bielefeld University. His work was also partially supported by Grant 96-01-01614 under the Russian Foundation for Basic Research.
PY - 2000/11
Y1 - 2000/11
N2 - Let G be an undirected graph and P={X1, ..., Xn} be a partition of V(G). Denote by G/P the graph which has vertex set {X1, ..., Xn}, edge set E, and is obtained from G by identifying vertices in each class Xi of the partition P. Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/P, w) is also a conservative graph. We characterize the conservative graphs (G/P, w), where 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 by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357-364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183-191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1-10), and a theorem of A. V. Kostochka (1994, in "Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109-123, Kluwer Academic, Dordrecht).
AB - Let G be an undirected graph and P={X1, ..., Xn} be a partition of V(G). Denote by G/P the graph which has vertex set {X1, ..., Xn}, edge set E, and is obtained from G by identifying vertices in each class Xi of the partition P. Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/P, w) is also a conservative graph. We characterize the conservative graphs (G/P, w), where 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 by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357-364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183-191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1-10), and a theorem of A. V. Kostochka (1994, in "Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109-123, Kluwer Academic, Dordrecht).
KW - Undirected graph; T-join; T-cut; conservative weighting
UR - http://www.scopus.com/inward/record.url?scp=0034311708&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034311708&partnerID=8YFLogxK
U2 - 10.1006/jctb.2000.1972
DO - 10.1006/jctb.2000.1972
M3 - Article
AN - SCOPUS:0034311708
SN - 0095-8956
VL - 80
SP - 202
EP - 217
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -