✦ LIBER ✦
Minor-order obstructions for the graphs of vertex cover 6
✍ Scribed by Michael J. Dinneen; Liu Xiong
- Publisher
- John Wiley and Sons
- Year
- 2002
- Tongue
- English
- Weight
- 240 KB
- Volume
- 41
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
We provide for the first time, a complete list of forbidden minors (obstructions) for the family of graphs with vertex cover 6. This study shows how to limit both the search space of graphs and improve the efficiency of an obstruction checking algorithm when restricted to k–VERTEX COVER graph families. In particular, our upper bounds 2__k__ + 1 (2__k__ + 2) on the maximum number of vertices for connected (disconnected) obstructions are shown to be sharp for all k > 0. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 163–178, 2002