Graph Minor
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if it does not contain the complete graph K5 nor the complete bipartite graph K3,3 as a minor. The Robertson–Seymour theorem states that the relation "being a minor of" is a well-quasi-ordering on the isomorphism classes of graphs, and implies that many other families of graphs have forbidden minor characterizations similar to that for the planar graphs.
Read more about Graph Minor: Definitions, Example, Major Results and Conjectures, Minor-closed Graph Families, Topological Minors, Immersion Minor, Algorithms
Famous quotes containing the words graph and/or minor:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“People are too apt to treat God as if he were a minor royalty.”
—Herbert Beerbohm, Sir Tree (1853–1917)