minorclosed

Minorclosed is a term in graph theory used to describe a class of graphs that is closed under taking graph minors. A graph H is a minor of a graph G if H can be obtained from G by deleting vertices and edges and by contracting edges. A class C of graphs is called minor-closed when, for every G in C, every minor of G also lies in C.

Because minors include subgraphs, a minor-closed class is in particular closed under taking subgraphs. The operation of edge contraction is central: contracting an edge uv merges its endpoints into a single vertex, possibly creating parallel edges; when working with simple graphs, parallel edges are often suppressed and loops removed.

Minor-closed classes arise naturally in structural graph theory. Examples include planar graphs, forests, outerplanar graphs, and series-parallel graphs. More generally, graphs of bounded genus or bounded treewidth form minor-closed families. Many natural graph properties are minor-closed, especially those preserved by edge deletion and contraction.

A central result is that minor-closed properties can be described by a finite set of forbidden minors: a graph belongs to a given minor-closed class if and only if it contains none of a finite list of graphs as minors. This follows from the Graph Minors Project of Robertson and Seymour. The simplest illustration is planarity, which is characterized by the absence of K5 and K3,3 as minors (Kuratowski's theorem).

Not all natural properties are minor-closed; for example, having a Hamiltonian cycle is not preserved under contraction. Minor-closed theory provides powerful tools for both structure and algorithms in graph theory.