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.^[1]

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 $K_{r},\,n\geq r\geq 3$ .^[2]

An equivalent problem is how many edges in an n-vertex graph guarantee that it has a subgraph isomorphic to G?^[3]

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.^[4]

References

^ 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.

[bollobas-1] Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics, Béla Bollobás, 1986, ISBN 0-521-33703-8, p. 53, 54

[2] . 254

[3] "Modern Graph Theory", by Béla Bollobás, 1998, ISBN 0-387-98488-7, p. 103

[4] Handbook of Discrete and Combinatorial Mathematics By Kenneth H. Rosen, John G. Michaels p. 590

[1]

[2]

[3]

[4]

See also

References