Forbidden subgraph problem
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges in an n-vertex graph which does not have a subgraph isomorphic to G. In this context, G is called a forbidden subgraph.
It is also called the Turán-type problem and the corresponding number is called the Turán number for graph G. It is called so in memory of Pál Turán, who determined this number for all n and all complete graphs .
An equivalent problem is how many edges in an n-vertex graph guarantee that it has a subgraph isomorphic to G?
The problem may be generalized for a set of forbidden subgraphs S: find the maximal number of edges in an n-vertex graph which does not have a subgraph isomorphic to any graph form S.
- Biclique-free graph
- Erdős–Hajnal conjecture
- Turán number
- Subgraph isomorphism problem
- Forbidden graph characterization
- Zarankiewicz problem
- Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Béla Bollobás, 1986, ISBN 0-521-33703-8, p. 53, 54
- p. 254
- "Modern Graph Theory", by Béla Bollobás, 1998, ISBN 0-387-98488-7, p. 103
- Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels p. 590
|This combinatorics-related article is a stub. You can help Wikipedia by expanding it.|