Vertex set partitions preserving conservativeness

A. A. Ageev, A. V. Kostochka

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)202-217
Number of pages16
JournalJournal of Combinatorial Theory. Series B
Issue number2
StatePublished - Nov 2000


  • Undirected graph; T-join; T-cut; conservative weighting

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Vertex set partitions preserving conservativeness'. Together they form a unique fingerprint.

Cite this