A forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures. Families vary in the nature of what is forbidden. In general, a structure G is a member of a family if and only if a forbidden substructure is not contained in G. The forbidden substructure might simply be a subgraph, or a substructure from which one might derive (via, e.g., edge contraction or subdivision) that which is forbidden. Thus, the forbidden structure might be one of:
- subgraphs,
- homeomorphic subgraphs (also called topological minors).
- induced subgraphs,
- graph minors,
Such forbidden structures can also be called obstruction sets.
Forbidden graph characterizations are utilized in combinatorial algorithms, often for identifying a structure. Such methods can provide a polynomial-time algorithm for determining a graph's membership in a specific family (i.e., a polynomial-time implementation of an indicator function).
A well-known characterization of this kind is Kuratowski's theorem that provides two forbidden homeomorphic subgraphs, using which, one may determine a graph's planarity. Another is the Robertson–Seymour theorem that proves the existence of a forbidden minor characterization for several graph families.
Read more about Forbidden Graph Characterization: List of Forbidden Characterizations For Graphs and Hypergraphs
Famous quotes containing the words forbidden and/or graph:
“I am forbidden sugar, fat, and alcohol. So hooray, I guess, for oatmeal, lemon juice, and chicken soup.”
—Mason Cooley (b. 1927)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)