Vertex Set Partitions Preserving Conservativeness
✍ Scribed by A.A. Ageev; A.V. Kostochka
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 146 KB
- Volume
- 80
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
Denote by GÂP the graph which has vertex set [X 1 , ..., X n ], edge set E, and is obtained from G by identifying vertices in each class X i 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.