Subgraphs, induced subgraphs and spanning subgraphs

Depends on

• A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Used by

• A linearly large induced subgraph of a graph with few induced copies again has a linearly large restricted set Corollary
• Every nonempty hereditary graph class contains the null graph Corollary
• For every λ>0 a bounded number of disjoint ε-restricted sets covers all but λ|V(G)| vertices of an H-free graph Corollary
• The connected components of a graph partition its vertex set and are its maximal connected subgraphs Corollary
• An induced subgraph of a prime graph need not be prime Counterexample
• K₃ contains P₃ as a subgraph but not as an induced subgraph Counterexample
• The class of connected graphs is not hereditary Counterexample
• The class of regular graphs is not hereditary Counterexample
• A blockade-rainbow induced copy Definition
• A decomposition of a graph's edge set into complete bipartite subgraphs Definition
• A perfect graph Definition
• A tau-critical graph Definition
• Anticonnected graphs and anticonnected components Definition
• c-sparse, c-dense and c-restricted vertex sets Definition
• Cliques, stable sets, the clique number ω(G) and stability number α(G) Definition
• Connected graphs and connected components defined by the existence of vertex paths Definition
• Induced embeddings and induced copies of a graph Definition
• Kempe chains as connected components induced by two colour classes Definition
• Minimal forbidden induced subgraphs and forbidden bases Definition
• Modular partitions and the quotient graph they define Definition
• Modules of a graph, and the trivial modules Definition
• Ordinary-subgraph extremal number ex(n,H), Turán graph T_n,r, and balanced blowup H[s] Definition
• Perfect graphs Definition
• Plane embeddings of finite simple graphs, their faces, facial boundary walks and lengths (counting a bridge twice), and planar graphs Definition
• Spanning trees of a graph Definition
• Substituting one graph for a vertex of another Definition
• The complete connection of two disjoint graphs Definition
• The star-expansion of a graph Definition
• Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors Definition
• A worked graph records vertex deletion, edge deletion, edge contraction and the resulting minor model Example
• A complete connection of two perfect graphs is perfect Lemma
• A disjoint union of two perfect graphs is perfect Lemma
• A module of G[M] is a module of G whenever M is a module of G Lemma
• A set is c-sparse exactly when the maximum degree of the graph it induces is at most c times its size Lemma
• A subset occupying at least a λ fraction of a c-sparse set is (c/λ)-sparse Lemma
• Adding an edge between two nonadjacent vertices of a tree creates exactly one cycle Lemma
• An induced copy of H₂ inside the extension set of an induced embedding of H₁-v yields an induced copy of H₁ with H₂ substituted for v Lemma
• Every face of a plane subgraph contains each face of the original graph that it meets Lemma
• Every induced subgraph of a cograph is a cograph Lemma
• G[W]=Ḡ[W] for every vertex set W Lemma

…and 27 more results.

Dependency tree · two levels

2 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

• R. Diestel, Graph Theory, Chapter 1 preview (standard reference, not scraped)