Obstructions for the Graphs of Vertex Cover Seven
Michael J. Dinneen, Ralph Versteegen · ResearchSpace (University of Auckland) · 2012
In this paper we present an optimized procedure for computing the minor-order obstructions for graphs of vertex cover at most $k$. This extends the earlier method and results of Cattell and Dinneen in 1994, for $k \leq 5$. Here we extended the known set of forbidden graphs for $k \leq 7$. To help reduce the size of these sets, we also mention some proposals for finding minimal forbidden graphs for other ``stronger'' graph partial orders such as the $Y$-$\Delta$ and $H$-bowtie orders. We briefly mention our plans to incorporate these new features within our distributed computational framework (aka, VACS) for computing obstruction within the universe of bounded pathwidth and treewidth.