Live briefing
Everything about Forbidden subgraph problem
In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph, find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to. In this context, is called a forbidden subgraph. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Forbidden subgraph problemA 5-minute orientation
- Skim a recent paper: The spectral Turán problem about graphs of given size with forbidden subgraphsInfluential work since 2022
- Pick up a classic book: Graph-Theoretic Concepts in Computer ScienceThe most-reprinted book on the subject
- Read the landmark paper: On the forbidden induced subgraph sandwich problemCited 11 times
- Go sideways: Erdős–Stone theoremA closely related topic
- Go sideways: Pseudorandom graphA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
On the forbidden induced subgraph sandwich problem
The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
On the forbidden induced subgraph probe and sandwich problems
A General Method for Forbidden Induced Subgraph Sandwich Problem NP-completeness
A complete complexity dichotomy for the edge 3-colorability problem and a single 9-edge forbidden subgraph
🆕 Influential since 2022
📚 Books worth reading
Graph-Theoretic Concepts in Computer ScienceMartin Charles Golumbic · 2012
Discrete MathmaticsR. K. Bisht, H. S. Dhami · 2015
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Erdős–Stone theorem In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán's theorem to bound the number of edges in an H-free graph…
- Pseudorandom graph In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete…
- Homomorphism density In the mathematical field of extremal graph theory, homomorphism density with respect to a graph H {\displaystyle H} is a parameter t ( H , − ) {\displaystyle…
- Dependent random choice In mathematics, dependent random choice is a probabilistic technique that shows how to find a large set of vertices in a dense graph such that every small…
- Turán graph The Turán graph, denoted by T ( n , r ) {\displaystyle T(n,r)} , is a complete multipartite graph; it is formed by partitioning a set of n {\displaystyle…
- Sidorenko's conjecture Sidorenko's conjecture is a major conjecture in the field of extremal graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture…
- Flag algebra Flag algebras are an important computational tool in the field of graph theory which have a wide range of applications in homomorphism density and related…
- Alon–Boppana bound In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a d {\displaystyle…