Excluded Minor Theorems
by
J. Chlebíková
Bratislava

A typical excluded minor theorem characterizes the structure of the class of graphs that do not contain a specified graph (or graphs) as a minor. The structural information can then be used to obtain further information about the class of graphs. For example, Wagner's reformulation of Kuratowski's theorem states that planar graphs are exactly the class of graphs without K₅ or K_{3, 3} as a minor. Wagner also characterized classes of graphs excluding only one of these graphs. Other known excluded minor theorems include characterizations of graphs with no disjoint circuits (Dirac, Lovász) and graphs with no V₈-minor (Robertson). Maharry characterized all graphs that do not have a cube as a minor. We proved some new excluded minor theorems, based mostly on the Seymour's splitter theorem. We say that a graph is semiplanar, if it can be obtained from planar graphs by repeatedly applying the operation of (clique) sums. It can be proved that all semiplanar graphs can be obtained from planar graphs by means of <= 3-sums. Let K₅^* denote a graph constructed from K₅ by splitting a vertex. Let K_{3, 3}^* denote a graph constructed from K_{3, 3} by adding an edge.

Date received: May 26, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafd-06.