Forbidden graph characterization
- Forbidden graph characterization
A forbidden graph characterization is a method of specifying or describing a family of graphs whereby a graph belongs to the family in question if and only if for the graph in question certain graphs, called forbidden graphs, are not its "parts" of a specified kind, such as:
*subgraphs,
*graph minors,
*homeomorphic subgraphs
*spanning subgraphs
*induced subgraphs
The sets of forbidden graphs are also called obstruction sets.
The forbidden graph characterization has applications in the computational complexity theory, providing in any cases polynomial-time (although not necessarily most efficient) algorithms for testing whether a graph belongs to a given family.
An early characterization of this kind is the Kuratowski theorem for planar graphs.
The Robertson–Seymour theorem proves the existence of a forbidden minor characterization of a number of graph families.
List of forbidden characterizations
ee also
*Forbidden subgraph problem
References
Ļ
Wikimedia Foundation.
2010.
Look at other dictionaries:
Outerplanar graph — A maximal outerplanar graph and its 3 coloring. In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing.… … Wikipedia
Line graph — This article is about the mathematical concept. For statistical presentation method, see line chart. In graph theory, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name… … Wikipedia
Line graph of a hypergraph — The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two edges adjacent when they have nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph of … Wikipedia
Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 … Wikipedia
Comparability graph — In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable… … Wikipedia
Colin de Verdière graph invariant — Colin de Verdière s invariant is a graph parameter μ(G) for any graph G introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.[1] Contents … Wikipedia
Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… … Wikipedia
Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and … Wikipedia
Circular-arc graph — A circular arc graph (left) and a corresponding arc model (right). In graph theory, a circular arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of… … Wikipedia
Split graph — In graph theory, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer in two papers in 1977, and independently introduced by Tyshkevich and… … Wikipedia
