Graph properties and obstruction sets

Abstract

The Wagner Conjecture has been proven and is now called the Graph Minor Theorem: we know that the set of forbidden minors obstructing a minor closed graph property is finite. We define operations that reverse the standard minor operations: given a graph G the operations create sets of graphs that have G as a minor, adjacent in the partial order. In particular, we add graphs from the obstruction set to the property set and find the obstruction set for the new property set. We also perform the operations of union and intersection on obstruction sets and property sets and using a series of examples, the obstruction set for the union of two properties is investigated. While it is not trivial to identify a general method for finding such obstruction sets, some structure is observed.