Live briefing
Everything about Forbidden graph characterization
Describing a family of graphs by excluding certain (sub)graphs
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Forbidden graph characterizationA 5-minute orientation
- Skim a recent paper: Characterizing Forbidden Pairs for the Edge-Connectivity of a Connected Graph to Be Its Minimum DegreeInfluential work since 2022
- Pick up a classic book: Graph-Theoretic Concepts in Computer ScienceThe most-reprinted book on the subject
- Read the landmark paper: Hereditary Domination in Graphs: Characterization with Forbidden Induced SubgraphsCited 30 times
- Go sideways: Graph minorA closely related topic
- Go sideways: TreewidthA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
On forbidden subdivision characterizations of graph classes
A forbidden subgraph characterization of some graph classes using betweenness axioms
Characterization of forbidden subgraphs for the existence of even factors in a graph
The forbidden subgraph characterization of directed vertex graphs
A forbidden subgraph characterization of line-polar bipartite graphs
Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
Graph classes characterized both by forbidden subgraphs and degree sequences
🆕 Influential since 2022
Characterizing Forbidden Pairs for the Edge-Connectivity of a Connected Graph to Be Its Minimum Degree
Forbidden induced subgraph characterization of circle graphs within split graphs
Characterize forbidden pairs forcing a 2-factorable graph to be hamiltonian
Non-existence of forbidden subgraph characterization of $H$-line graphs
A characterization of almost-2-distance-hereditary graphs in terms of their forbidden subgraphs
📚 Books worth reading
Graph-Theoretic Concepts in Computer ScienceMartin Charles Golumbic · 2012
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Graph minor In graph theory, an undirected graph H is called a minor of the undirected graph G if H can be formed from G by deleting edges and vertices and by contracting…
- Treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest…
- Branch-decomposition In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree…
- Apollonian network In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller…
- Pathwidth In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number…
- Kuratowski's theorem In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states…
- Dense graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected…
- Planar cover In graph theory, a planar cover of a finite graph G is a finite covering graph of G that is itself a planar graph. Every graph that can be embedded into…