Mathematics Commons^™

Obstruction Sets For Classes Of Cubic Graphs, Joshua Hughes

Doctoral Dissertations

This dissertation establishes two theorems which characterize the set of minimal obstructions for two classes of graphs. A minimal obstruction for a class of graphs is a graph that is not in the class but every graph that it properly contains, under some containment relation, is in the class. In Chapter 2, we provide a characterization of the class of cubic outer-planar graphs in terms of its minimal obstructions which are also called cubic obstructions in this setting. To do this, we first show that all the obstructions containing loops can be obtained from the complete set of loopless obstructions …