Forbidden graph characterization (nonfiction)

Forbidden induced subgraphs for the indifference graphs: the claw, sun, and net (top, left–right) and cycles of length four or more (bottom).

In graph theory, a branch of mathematics, a forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures, by specifying substructures that are forbidden from existing within any graph in the family.

Different families vary in the nature of what is forbidden. In general, a structure G is a member of a family F if and only if a forbidden substructure is not contained in G. The forbidden substructure might be one of:

• subgraphs, smaller graphs obtained from subsets of the vertices and edges of a larger graph,

induced subgraphs, smaller graphs obtained by selecting a subset of the vertices and using all edges with both endpoints in that subset,

• homeomorphic subgraphs (also called topological minors), smaller graphs obtained from subgraphs by collapsing paths of degree-two vertices to single edges, or
• graph minors, smaller graphs obtained from subgraphs by arbitrary edge contractions.

The set of structures that are forbidden from belonging to a given graph family can also be called an obstruction set for that family.

Forbidden graph characterizations may be used in algorithms for testing whether a graph belongs to a given family. In many cases, it is possible to test in polynomial time whether a given graph contains any of the members of the obstruction set, and therefore whether it belongs to the family defined by that obstruction set.

In order for a family to have a forbidden graph characterization, with a particular type of substructure, the family must be closed under substructures. That is, every substructure (of a given type) of a graph in the family must be another graph in the family. Equivalently, if a graph is not part of the family, all larger graphs containing it as a substructure must also be excluded from the family. When this is true, there always exists an obstruction set (the set of graphs that are not in the family but whose smaller substructures all belong to the family). However, for some notions of what a substructure is, this obstruction set could be infinite. The Robertson–Seymour theorem proves that, for the particular case of graph minors, a family that is closed under minors always has a finite obstruction set.

Nonfiction cross-reference

• Mathematics (nonfiction)
• Pál Turán (nonfiction)

External links:

• Forbidden graph characterization @ Wikipedia

Attribution: