Namespaces
Variants
Actions

Difference between revisions of "Minor of a graph"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎References: expand bibliodata)
m (tex encoded by computer)
 
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641101.png" /> be a [[Graph|graph]] (possibly with loops and multiple edges). A minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641102.png" /> is any graph obtained by a succession of the following operations:
+
<!--
 +
m0641101.png
 +
$#A+1 = 48 n = 0
 +
$#C+1 = 48 : ~/encyclopedia/old_files/data/M064/M.0604110 Minor of a graph
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
Let  $  G $
 +
be a [[Graph|graph]] (possibly with loops and multiple edges). A minor of $  G $
 +
is any graph obtained by a succession of the following operations:
  
 
i) deletion of a single edge;
 
i) deletion of a single edge;
Line 7: Line 21:
 
iii) removal of an isolated vertex.
 
iii) removal of an isolated vertex.
  
The graph minor theorem of N. Robertson and P.D. Seymour says the following. Given an infinite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641103.png" /> of finite graphs, there are indices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641104.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641105.png" /> is (isomorphic to) a minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641106.png" />. This was conjectured by K. Wagner (Wagner's well-quasi-ordering conjecture).
+
The graph minor theorem of N. Robertson and P.D. Seymour says the following. Given an infinite sequence $  G _ {1} , G _ {2} \dots $
 +
of finite graphs, there are indices $  i < j $
 +
such that $  G _ {i} $
 +
is (isomorphic to) a minor of $  G _ {j} $.  
 +
This was conjectured by K. Wagner (Wagner's well-quasi-ordering conjecture).
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641107.png" /> be any property of a graph which is closed under taking minors. For instance, the property of being imbeddable in a compact Riemann surface. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641108.png" /> be the set of all minor-minimal isomorphism classes of graphs not possessing property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m0641109.png" />. Then the graph minor theorem says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411010.png" /> is finite. This implies that property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411011.png" /> is characterized by saying that a graph has property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411012.png" /> if and only if it does not contain a minor from the finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411013.png" />. In the case of the property  "planar"  the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411014.png" /> is given by the two graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411016.png" />, cf. [[Kuratowski graph|Kuratowski graph]].
+
Let $  P $
 +
be any property of a graph which is closed under taking minors. For instance, the property of being imbeddable in a compact Riemann surface. Let $  L $
 +
be the set of all minor-minimal isomorphism classes of graphs not possessing property $  P $.  
 +
Then the graph minor theorem says that $  L $
 +
is finite. This implies that property $  P $
 +
is characterized by saying that a graph has property $  P $
 +
if and only if it does not contain a minor from the finite set $  L $.  
 +
In the case of the property  "planar"  the set $  L $
 +
is given by the two graphs $  K _ {3,3} $
 +
and $  K _ {5} $,  
 +
cf. [[Kuratowski graph|Kuratowski graph]].
  
 
The finite forms of the graph minor theorem are as follows:
 
The finite forms of the graph minor theorem are as follows:
  
a) For all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411017.png" /> there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411018.png" /> such that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411019.png" />-tuples of graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411020.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411021.png" /> there is a pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411022.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411023.png" /> isomorphic to a minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411024.png" />. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411025.png" /> denotes the sum of the number of vertices and the number of edges of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411026.png" />.
+
a) For all $  k $
 +
there is an $  n $
 +
such that for $  n $-
 +
tuples of graphs $  G _ {1} \dots G _ {n} $
 +
with $  | G _ {i} | \leq  k + i $
 +
there is a pair $  i < j $
 +
with $  G _ {i} $
 +
isomorphic to a minor of $  G _ {j} $.  
 +
Here $  | G _ {i} | $
 +
denotes the sum of the number of vertices and the number of edges of $  G _ {i} $.
  
b) For all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411027.png" /> there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411028.png" /> such that for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411029.png" />-tuples of graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411030.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411031.png" /> there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411032.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411033.png" /> is isomorphic to a minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411034.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411035.png" />.
+
b) For all $  k $
 +
there is an $  n $
 +
such that for all $  n $-
 +
tuples of graphs $  G _ {1} \dots G _ {n} $
 +
with $  | G _ {i} | \leq  i $
 +
there are $  i _ {1} < \dots < i _ {k} $
 +
such that $  G _ {i _ {j}  } $
 +
is isomorphic to a minor of $  G _ {i _ {j+} 1 }  $
 +
for all $  j = 1 \dots k - 1 $.
  
Wagner's conjecture does not hold, in general, for infinite graphs, in the sense that there is a sequence of infinite graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411036.png" /> such that for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411038.png" /> is not a minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411039.png" />. The conjecture is open (1988) for countable graphs.
+
Wagner's conjecture does not hold, in general, for infinite graphs, in the sense that there is a sequence of infinite graphs $  G _ {1} , G _ {2} \dots $
 +
such that for all $  i \neq j $,  
 +
$  G _ {i} $
 +
is not a minor of $  G _ {j} $.  
 +
The conjecture is open (1988) for countable graphs.
  
A consequence (application) is that each graph property that is closed under taking minors can be tested in polynomial time. So, for instance, planarity can be tested in polynomial time. Further, there exists a polynomial-time algorithm for the following problem: Given a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411040.png" /> and vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411041.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411042.png" />, find paths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411043.png" /> so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411044.png" /> connects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411046.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411047.png" /> and such that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m064/m064110/m06411048.png" /> are vertex disjoint. Such problems arise in VLSI design.
+
A consequence (application) is that each graph property that is closed under taking minors can be tested in polynomial time. So, for instance, planarity can be tested in polynomial time. Further, there exists a polynomial-time algorithm for the following problem: Given a graph $  G $
 +
and vertices $  r _ {1} , s _ {1} \dots r _ {k} , s _ {k} $
 +
of $  G $,  
 +
find paths $  P _ {1} \dots P _ {k} $
 +
so that $  P _ {i} $
 +
connects $  r _ {i} $
 +
and $  s _ {i} $
 +
for all $  i = 1 \dots k $
 +
and such that the $  P _ {1} \dots P _ {k} $
 +
are vertex disjoint. Such problems arise in VLSI design.
  
 
====References====
 
====References====

Latest revision as of 08:00, 6 June 2020


Let $ G $ be a graph (possibly with loops and multiple edges). A minor of $ G $ is any graph obtained by a succession of the following operations:

i) deletion of a single edge;

ii) contraction of a single edge;

iii) removal of an isolated vertex.

The graph minor theorem of N. Robertson and P.D. Seymour says the following. Given an infinite sequence $ G _ {1} , G _ {2} \dots $ of finite graphs, there are indices $ i < j $ such that $ G _ {i} $ is (isomorphic to) a minor of $ G _ {j} $. This was conjectured by K. Wagner (Wagner's well-quasi-ordering conjecture).

Let $ P $ be any property of a graph which is closed under taking minors. For instance, the property of being imbeddable in a compact Riemann surface. Let $ L $ be the set of all minor-minimal isomorphism classes of graphs not possessing property $ P $. Then the graph minor theorem says that $ L $ is finite. This implies that property $ P $ is characterized by saying that a graph has property $ P $ if and only if it does not contain a minor from the finite set $ L $. In the case of the property "planar" the set $ L $ is given by the two graphs $ K _ {3,3} $ and $ K _ {5} $, cf. Kuratowski graph.

The finite forms of the graph minor theorem are as follows:

a) For all $ k $ there is an $ n $ such that for $ n $- tuples of graphs $ G _ {1} \dots G _ {n} $ with $ | G _ {i} | \leq k + i $ there is a pair $ i < j $ with $ G _ {i} $ isomorphic to a minor of $ G _ {j} $. Here $ | G _ {i} | $ denotes the sum of the number of vertices and the number of edges of $ G _ {i} $.

b) For all $ k $ there is an $ n $ such that for all $ n $- tuples of graphs $ G _ {1} \dots G _ {n} $ with $ | G _ {i} | \leq i $ there are $ i _ {1} < \dots < i _ {k} $ such that $ G _ {i _ {j} } $ is isomorphic to a minor of $ G _ {i _ {j+} 1 } $ for all $ j = 1 \dots k - 1 $.

Wagner's conjecture does not hold, in general, for infinite graphs, in the sense that there is a sequence of infinite graphs $ G _ {1} , G _ {2} \dots $ such that for all $ i \neq j $, $ G _ {i} $ is not a minor of $ G _ {j} $. The conjecture is open (1988) for countable graphs.

A consequence (application) is that each graph property that is closed under taking minors can be tested in polynomial time. So, for instance, planarity can be tested in polynomial time. Further, there exists a polynomial-time algorithm for the following problem: Given a graph $ G $ and vertices $ r _ {1} , s _ {1} \dots r _ {k} , s _ {k} $ of $ G $, find paths $ P _ {1} \dots P _ {k} $ so that $ P _ {i} $ connects $ r _ {i} $ and $ s _ {i} $ for all $ i = 1 \dots k $ and such that the $ P _ {1} \dots P _ {k} $ are vertex disjoint. Such problems arise in VLSI design.

References

[a1] H. Friedman, N. Robertson, P.D. Seymour, "The metamathematics of the graph minor theorem" Logic and combinatorics (ed. S.G. Simpson) Contemporary Math. 65, Amer. Math. Soc. (1987) pp. 229–261 Zbl 0635.03060
[a2] N. Robertson, P.D. Seymour, "Graph minors - a survey" I. Anderson (ed.) , Surveys in Combinatorics 1985 , Cambridge Univ. Press (1985) pp. 153–171 Zbl 0568.05025
[a3] R. Thomas, "A counter-example to "Wagner's conjecture" for infinite graphs" Math. Proc. Cambridge Philos. Soc. , 103 (1988) pp. 55–57 Zbl 0647.05054
How to Cite This Entry:
Minor of a graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Minor_of_a_graph&oldid=47855