Graph minor

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3.[1] The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.[2] For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time;[3] together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.[4]

Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have H as a minor may be formed by gluing together simpler pieces, and Hadwiger's conjecture relating the inability to color a graph to the existence of a large complete graph as a minor of it. Important variants of graph minors include the topological minors and immersion minors.

  1. ^ Lovász (2006), p. 77; Wagner (1937a).
  2. ^ Lovász (2006), theorem 4, p. 78; Robertson & Seymour (2004).
  3. ^ Cite error: The named reference rs95 was invoked but never defined (see the help page).
  4. ^ Cite error: The named reference fl88 was invoked but never defined (see the help page).