In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. Here, "contracting an edge" means removing the edge and identifying its two endpoints, keeping all other edges.
For example, the graph
* | *--*--* | *
is a minor of
* /| *-*--*-*-* |/ *
(the outer edges are removed, the long middle edge is contracted).
The relation "being a minor of" is a partial order on the isomorphism classes of graphs.
Many classes of graphs can be characterized by "forbidden minors": a graph belongs to the class if and only if it does not have a minor from a certain specified list. The best-known example is Kuratowski's theorem for the characterization of planar graphs. The general situation is described by the Robertson-Seymour theorem.
Another deep result by Robertson-Seymour states that if any infinite list G1, G2,... of finite graphs is given, then there always exists two indices i < j such that Gi is a minor of Gj.
In linear algebra, there is a different unrelated meaning of the word minor. See minor (linear algebra).
This theorem is often referred to as the deepest result in graphtheory.
It was proven by Robertson and Seymour in 1988 as the culminating result of a long series of articles, and the proof was recently published in the Journal of Combinatorial Theory series B. It resolves Wagner's conjecture in the affirmative and leads to an important generalization of Kuratowski's theorem.
This is version 13 of graphminor theorem, born on 2003-11-23, modified 2006-10-10.
In graphtheory, a homeomorphism exists between two graphs G and G′ if there exists a graph H such that both G and G′ are subdivisions of that graph.
If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted in illustrations), then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the sense in which the term is used in topology.
In general, a subdivision of a graph G is a graph resulting from the subdivision of edges in G.
Feeds |
Contact