Abstract:
We provide for the first time a complete list of forbidden minors (obstructions)
for the family of graphs with vertex cover 6. This paper 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 2k + 1 (2k + 2) on the maximum number of
vertices for connected (disconnected) obstructions are shown to be sharp for all
k > 0.