Properties of vertex cover obstructions

AbstractWe study properties of the sets of minimal forbidden minors for the families of graphs having a vertex cover of size at most k. We denote this set by O(k-VERTEX COVER) and call it the set of obstructions. Our main result is to give a tight vertex bound of O(k-VERTEX COVER), and then confirm a conjecture made by Liu Xiong that there is a unique connected obstruction with maximum number of vertices for k-VERTEX COVER and this graph is C2k+1. We also find two iterative methods to generate graphs in O((k+1)-VERTEX COVER) from any graph in O(k-VERTEX COVER)