fbpx
Wikipedia

Robertson–Seymour theorem

January 21, 2023

In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem[1]) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering.[2] Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3,3 as minors.

The Robertson–Seymour theorem is named after mathematicians Neil Robertson and Paul D. Seymour, who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004.[3] Before its proof, the statement of the theorem was known as Wagner's conjecture after the German mathematician Klaus Wagner, although Wagner said he never conjectured it.[4]

A weaker result for trees is implied by Kruskal's tree theorem, which was conjectured in 1937 by Andrew Vázsonyi and proved in 1960 independently by Joseph Kruskal and S. Tarkowski.[5]

Statement

A minor of an undirected graph G is any graph that may be obtained from G by a sequence of zero or more contractions of edges of G and deletions of edges and vertices of G. The minor relationship forms a partial order on the set of all distinct finite undirected graphs, as it obeys the three axioms of partial orders: it is reflexive (every graph is a minor of itself), transitive (a minor of a minor of G is itself a minor of G), and antisymmetric (if two graphs G and H are minors of each other, then they must be isomorphic). However, if graphs that are isomorphic may nonetheless be considered as distinct objects, then the minor ordering on graphs forms a preorder, a relation that is reflexive and transitive but not necessarily antisymmetric.[6]

A preorder is said to form a well-quasi-ordering if it contains neither an infinite descending chain nor an infinite antichain.[7] For instance, the usual ordering on the non-negative integers is a well-quasi-ordering, but the same ordering on the set of all integers is not, because it contains the infinite descending chain 0, −1, −2, −3... Another example is the set of positive integers ordered by divisibility, which has no infinite descending chains, but where the prime numbers constitute an infinite antichain.

The Robertson–Seymour theorem states that finite undirected graphs and graph minors form a well-quasi-ordering. The graph minor relationship does not contain any infinite descending chain, because each contraction or deletion reduces the number of edges and vertices of the graph (a non-negative integer).[8] The nontrivial part of the theorem is that there are no infinite antichains, infinite sets of graphs that are all unrelated to each other by the minor ordering. If S is a set of graphs, and M is a subset of S containing one representative graph for each equivalence class of minimal elements (graphs that belong to S but for which no proper minor belongs to S), then M forms an antichain; therefore, an equivalent way of stating the theorem is that, in any infinite set S of graphs, there must be only a finite number of non-isomorphic minimal elements.

Another equivalent form of the theorem is that, in any infinite set S of graphs, there must be a pair of graphs one of which is a minor of the other.[8] The statement that every infinite set has finitely many minimal elements implies this form of the theorem, for if there are only finitely many minimal elements, then each of the remaining graphs must belong to a pair of this type with one of the minimal elements. And in the other direction, this form of the theorem implies the statement that there can be no infinite antichains, because an infinite antichain is a set that does not contain any pair related by the minor relation.

Forbidden minor characterizations

A family F of graphs is said to be closed under the operation of taking minors if every minor of a graph in F also belongs to F. If F is a minor-closed family, then let S be the class of graphs that are not in F (the complement of F). According to the Robertson–Seymour theorem, there exists a finite set H of minimal elements in S. These minimal elements form a forbidden graph characterization of F: the graphs in F are exactly the graphs that do not have any graph in H as a minor.[9] The members of H are called the excluded minors (or forbidden minors, or minor-minimal obstructions) for the family F.

For example, the planar graphs are closed under taking minors: contracting an edge in a planar graph, or removing edges or vertices from the graph, cannot destroy its planarity. Therefore, the planar graphs have a forbidden minor characterization, which in this case is given by Wagner's theorem: the set H of minor-minimal nonplanar graphs contains exactly two graphs, the complete graph K5 and the complete bipartite graph K3,3, and the planar graphs are exactly the graphs that do not have a minor in the set {K5, K3,3}.

The existence of forbidden minor characterizations for all minor-closed graph families is an equivalent way of stating the Robertson–Seymour theorem. For, suppose that every minor-closed family F has a finite set H of minimal forbidden minors, and let S be any infinite set of graphs. Define F from S as the family of graphs that do not have a minor in S. Then F is minor-closed and has a finite set H of minimal forbidden minors. Let C be the complement of F. S is a subset of C since S and F are disjoint, and H are the minimal graphs in C. Consider a graph G in H. G cannot have a proper minor in S since G is minimal in C. At the same time, G must have a minor in S, since otherwise G would be an element in F. Therefore, G is an element in S, i.e., H is a subset of S, and all other graphs in S have a minor among the graphs in H, so H is the finite set of minimal elements of S.

For the other implication, assume that every set of graphs has a finite subset of minimal graphs and let a minor-closed set F be given. We want to find a set H of graphs such that a graph is in F if and only if it does not have a minor in H. Let E be the graphs which are not minors of any graph in F, and let H be the finite set of minimal graphs in E. Now, let an arbitrary graph G be given. Assume first that G is in F. G cannot have a minor in H since G is in F and H is a subset of E. Now assume that G is not in F. Then G is not a minor of any graph in F, since F is minor-closed. Therefore, G is in E, so G has a minor in H.

Examples of minor-closed families

Main article: Forbidden graph characterization

The following sets of finite graphs are minor-closed, and therefore (by the Robertson–Seymour theorem) have forbidden minor characterizations:

Obstruction sets

 
The Petersen family, the obstruction set for linkless embedding.

Some examples of finite obstruction sets were already known for specific classes of graphs before the Robertson–Seymour theorem was proved. For example, the obstruction for the set of all forests is the loop graph (or, if one restricts to simple graphs, the cycle with three vertices). This means that a graph is a forest if and only if none of its minors is the loop (or, the cycle with three vertices, respectively). The sole obstruction for the set of paths is the tree with four vertices, one of which has degree 3. In these cases, the obstruction set contains a single element, but in general this is not the case. Wagner's theorem states that a graph is planar if and only if it has neither K5 nor K3,3 as a minor. In other words, the set {K5, K3,3} is an obstruction set for the set of all planar graphs, and in fact the unique minimal obstruction set. A similar theorem states that K4 and K2,3 are the forbidden minors for the set of outerplanar graphs.

Although the Robertson–Seymour theorem extends these results to arbitrary minor-closed graph families, it is not a complete substitute for these results, because it does not provide an explicit description of the obstruction set for any family. For example, it tells us that the set of toroidal graphs has a finite obstruction set, but it does not provide any such set. The complete set of forbidden minors for toroidal graphs remains unknown, but it contains at least 17,535 graphs.[11]

Polynomial time recognition

The Robertson–Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph h, there is a polynomial time algorithm for testing whether a graph has h as a minor. This algorithm's running time is cubic (in the size of the graph to check), though with a constant factor that depends superpolynomially on the size of the minor h. The running time has been improved to quadratic by Kawarabayashi, Kobayashi, and Reed.[12] As a result, for every minor-closed family F, there is polynomial time algorithm for testing whether a graph belongs to F: simply check whether the given graph contains h for each forbidden minor h in F’s obstruction set.[13]

However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm.[14] In many specific cases, checking whether a graph is in a given minor-closed family can be done more efficiently: for example, checking whether a graph is planar can be done in linear time.

Fixed-parameter tractability

For graph invariants with the property that, for each k, the graphs with invariant at most k are minor-closed, the same method applies. For instance, by this result, treewidth, branchwidth, and pathwidth, vertex cover, and the minimum genus of an embedding are all amenable to this approach, and for any fixed k there is a polynomial time algorithm for testing whether these invariants are at most k, in which the exponent in the running time of the algorithm does not depend on k. A problem with this property, that it can be solved in polynomial time for any fixed k with an exponent that does not depend on k, is known as fixed-parameter tractable.

However, this method does not directly provide a single fixed-parameter-tractable algorithm for computing the parameter value for a given graph with unknown k, because of the difficulty of determining the set of forbidden minors. Additionally, the large constant factors involved in these results make them highly impractical. Therefore, the development of explicit fixed-parameter algorithms for these problems, with improved dependence on k, has continued to be an important line of research.

Finite form of the graph minor theorem

Friedman, Robertson & Seymour (1987) showed that the following theorem exhibits the independence phenomenon by being unprovable in various formal systems that are much stronger than Peano arithmetic, yet being provable in systems much weaker than ZFC:

Theorem: For every positive integer n, there is an integer m so large that if G1, ..., Gm is a sequence of finite undirected graphs,
where each Gi has size at most n+i, then Gj ≤ Gk for some j < k.

(Here, the size of a graph is the total number of its vertices and edges, and ≤ denotes the minor ordering.)

See also

Notes

  1. ^ Bienstock & Langston (1995).
  2. ^ Robertson & Seymour (2004).
  3. ^ Robertson and Seymour (1983, 2004); Diestel (2005, p. 333).
  4. ^ Diestel (2005, p. 355).
  5. ^ Diestel (2005, pp. 335–336); Lovász (2005), Section 3.3, pp. 78–79.
  6. ^ E.g., see Bienstock & Langston (1995), Section 2, "well-quasi-orders".
  7. ^ Diestel (2005, p. 334).
  8. ^ a b Lovász (2005, p. 78).
  9. ^ Bienstock & Langston (1995), Corollary 2.1.1; Lovász (2005), Theorem 4, p. 78.
  10. ^ a b Lovász (2005, pp. 76–77).
  11. ^ Myrvold & Woodcock (2018).
  12. ^ Kawarabayashi, Kobayashi & Reed (2012)
  13. ^ Robertson & Seymour (1995); Bienstock & Langston (1995), Theorem 2.1.4 and Corollary 2.1.5; Lovász (2005), Theorem 11, p. 83.
  14. ^ Fellows & Langston (1988); Bienstock & Langston (1995), Section 6.

References

  • Bienstock, Daniel; Langston, Michael A. (1995), "Algorithmic implications of the graph minor theorem" (PDF), Network Models, Handbooks in Operations Research and Management Science, vol. 7, pp. 481–502, doi:10.1016/S0927-0507(05)80125-2.
  • Diestel, Reinhard (2005), "Minors, Trees, and WQO", Graph Theory (PDF) (Electronic Edition 2005 ed.), Springer, pp. 326–367.
  • Fellows, Michael R.; Langston, Michael A. (1988), "Nonconstructive tools for proving polynomial-time decidability", Journal of the ACM, 35 (3): 727–739, doi:10.1145/44483.44491.
  • Friedman, Harvey; Robertson, Neil; Seymour, Paul (1987), "The metamathematics of the graph minor theorem", in Simpson, S. (ed.), Logic and Combinatorics, Contemporary Mathematics, vol. 65, American Mathematical Society, pp. 229–261.
  • Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce (2012), "The disjoint paths problem in quadratic time" (PDF), Journal of Combinatorial Theory, Series B, 102 (2): 424–435, doi:10.1016/j.jctb.2011.07.004.
  • Lovász, László (2005), "Graph Minor Theory", Bulletin of the American Mathematical Society, New Series, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8.
  • Myrvold, Wendy; Woodcock, Jennifer (2018), "A Large Set of Torus Obstructions and How They Were Discovered", The Electronic Journal of Combinatorics, 25 (1): P1.16, doi:10.37236/3797.
  • Robertson, Neil; Seymour, Paul (1983), "Graph Minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5.
  • Robertson, Neil; Seymour, Paul (1995), "Graph Minors. XIII. The disjoint paths problem", Journal of Combinatorial Theory, Series B, 63 (1): 65–110, doi:10.1006/jctb.1995.1006.
  • Robertson, Neil; Seymour, Paul (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001.

External links

January 21, 2023
robertson, seymour, theorem, graph, theory, also, called, graph, minor, theorem, states, that, undirected, graphs, partially, ordered, graph, minor, relationship, form, well, quasi, ordering, equivalently, every, family, graphs, that, closed, under, minors, de. In graph theory the Robertson Seymour theorem also called the graph minor theorem 1 states that the undirected graphs partially ordered by the graph minor relationship form a well quasi ordering 2 Equivalently every family of graphs that is closed under minors can be defined by a finite set of forbidden minors in the same way that Wagner s theorem characterizes the planar graphs as being the graphs that do not have the complete graph K5 or the complete bipartite graph K3 3 as minors The Robertson Seymour theorem is named after mathematicians Neil Robertson and Paul D Seymour who proved it in a series of twenty papers spanning over 500 pages from 1983 to 2004 3 Before its proof the statement of the theorem was known as Wagner s conjecture after the German mathematician Klaus Wagner although Wagner said he never conjectured it 4 A weaker result for trees is implied by Kruskal s tree theorem which was conjectured in 1937 by Andrew Vazsonyi and proved in 1960 independently by Joseph Kruskal and S Tarkowski 5 Contents 1 Statement 2 Forbidden minor characterizations 3 Examples of minor closed families 4 Obstruction sets 5 Polynomial time recognition 6 Fixed parameter tractability 7 Finite form of the graph minor theorem 8 See also 9 Notes 10 References 11 External linksStatement EditA minor of an undirected graph G is any graph that may be obtained from G by a sequence of zero or more contractions of edges of G and deletions of edges and vertices of G The minor relationship forms a partial order on the set of all distinct finite undirected graphs as it obeys the three axioms of partial orders it is reflexive every graph is a minor of itself transitive a minor of a minor of G is itself a minor of G and antisymmetric if two graphs G and H are minors of each other then they must be isomorphic However if graphs that are isomorphic may nonetheless be considered as distinct objects then the minor ordering on graphs forms a preorder a relation that is reflexive and transitive but not necessarily antisymmetric 6 A preorder is said to form a well quasi ordering if it contains neither an infinite descending chain nor an infinite antichain 7 For instance the usual ordering on the non negative integers is a well quasi ordering but the same ordering on the set of all integers is not because it contains the infinite descending chain 0 1 2 3 Another example is the set of positive integers ordered by divisibility which has no infinite descending chains but where the prime numbers constitute an infinite antichain The Robertson Seymour theorem states that finite undirected graphs and graph minors form a well quasi ordering The graph minor relationship does not contain any infinite descending chain because each contraction or deletion reduces the number of edges and vertices of the graph a non negative integer 8 The nontrivial part of the theorem is that there are no infinite antichains infinite sets of graphs that are all unrelated to each other by the minor ordering If S is a set of graphs and M is a subset of S containing one representative graph for each equivalence class of minimal elements graphs that belong to S but for which no proper minor belongs to S then M forms an antichain therefore an equivalent way of stating the theorem is that in any infinite set S of graphs there must be only a finite number of non isomorphic minimal elements Another equivalent form of the theorem is that in any infinite set S of graphs there must be a pair of graphs one of which is a minor of the other 8 The statement that every infinite set has finitely many minimal elements implies this form of the theorem for if there are only finitely many minimal elements then each of the remaining graphs must belong to a pair of this type with one of the minimal elements And in the other direction this form of the theorem implies the statement that there can be no infinite antichains because an infinite antichain is a set that does not contain any pair related by the minor relation Forbidden minor characterizations EditA family F of graphs is said to be closed under the operation of taking minors if every minor of a graph in F also belongs to F If F is a minor closed family then let S be the class of graphs that are not in F the complement of F According to the Robertson Seymour theorem there exists a finite set H of minimal elements in S These minimal elements form a forbidden graph characterization of F the graphs in F are exactly the graphs that do not have any graph in H as a minor 9 The members of H are called the excluded minors or forbidden minors or minor minimal obstructions for the family F For example the planar graphs are closed under taking minors contracting an edge in a planar graph or removing edges or vertices from the graph cannot destroy its planarity Therefore the planar graphs have a forbidden minor characterization which in this case is given by Wagner s theorem the set H of minor minimal nonplanar graphs contains exactly two graphs the complete graph K5 and the complete bipartite graph K3 3 and the planar graphs are exactly the graphs that do not have a minor in the set K5 K3 3 The existence of forbidden minor characterizations for all minor closed graph families is an equivalent way of stating the Robertson Seymour theorem For suppose that every minor closed family F has a finite set H of minimal forbidden minors and let S be any infinite set of graphs Define F from S as the family of graphs that do not have a minor in S Then F is minor closed and has a finite set H of minimal forbidden minors Let C be the complement of F S is a subset of C since S and F are disjoint and H are the minimal graphs in C Consider a graph G in H G cannot have a proper minor in S since G is minimal in C At the same time G must have a minor in S since otherwise G would be an element in F Therefore G is an element in S i e H is a subset of S and all other graphs in S have a minor among the graphs in H so H is the finite set of minimal elements of S For the other implication assume that every set of graphs has a finite subset of minimal graphs and let a minor closed set F be given We want to find a set H of graphs such that a graph is in F if and only if it does not have a minor in H Let E be the graphs which are not minors of any graph in F and let H be the finite set of minimal graphs in E Now let an arbitrary graph G be given Assume first that G is in F G cannot have a minor in H since G is in F and H is a subset of E Now assume that G is not in F Then G is not a minor of any graph in F since F is minor closed Therefore G is in E so G has a minor in H Examples of minor closed families EditMain article Forbidden graph characterization The following sets of finite graphs are minor closed and therefore by the Robertson Seymour theorem have forbidden minor characterizations forests linear forests disjoint unions of path graphs pseudoforests and cactus graphs planar graphs outerplanar graphs apex graphs formed by adding a single vertex to a planar graph toroidal graphs and the graphs that can be embedded on any fixed two dimensional manifold 10 graphs that are linklessly embeddable in Euclidean 3 space and graphs that are knotlessly embeddable in Euclidean 3 space 10 graphs with a feedback vertex set of size bounded by some fixed constant graphs with Colin de Verdiere graph invariant bounded by some fixed constant graphs with treewidth pathwidth or branchwidth bounded by some fixed constant Obstruction sets Edit The Petersen family the obstruction set for linkless embedding Some examples of finite obstruction sets were already known for specific classes of graphs before the Robertson Seymour theorem was proved For example the obstruction for the set of all forests is the loop graph or if one restricts to simple graphs the cycle with three vertices This means that a graph is a forest if and only if none of its minors is the loop or the cycle with three vertices respectively The sole obstruction for the set of paths is the tree with four vertices one of which has degree 3 In these cases the obstruction set contains a single element but in general this is not the case Wagner s theorem states that a graph is planar if and only if it has neither K5 nor K3 3 as a minor In other words the set K5 K3 3 is an obstruction set for the set of all planar graphs and in fact the unique minimal obstruction set A similar theorem states that K4 and K2 3 are the forbidden minors for the set of outerplanar graphs Although the Robertson Seymour theorem extends these results to arbitrary minor closed graph families it is not a complete substitute for these results because it does not provide an explicit description of the obstruction set for any family For example it tells us that the set of toroidal graphs has a finite obstruction set but it does not provide any such set The complete set of forbidden minors for toroidal graphs remains unknown but it contains at least 17 535 graphs 11 Polynomial time recognition EditThe Robertson Seymour theorem has an important consequence in computational complexity due to the proof by Robertson and Seymour that for each fixed graph h there is a polynomial time algorithm for testing whether a graph has h as a minor This algorithm s running time is cubic in the size of the graph to check though with a constant factor that depends superpolynomially on the size of the minor h The running time has been improved to quadratic by Kawarabayashi Kobayashi and Reed 12 As a result for every minor closed family F there is polynomial time algorithm for testing whether a graph belongs to F simply check whether the given graph contains h for each forbidden minor h in F s obstruction set 13 However this method requires a specific finite obstruction set to work and the theorem does not provide one The theorem proves that such a finite obstruction set exists and therefore the problem is polynomial because of the above algorithm However the algorithm can be used in practice only if such a finite obstruction set is provided As a result the theorem proves that the problem can be solved in polynomial time but does not provide a concrete polynomial time algorithm for solving it Such proofs of polynomiality are non constructive they prove polynomiality of problems without providing an explicit polynomial time algorithm 14 In many specific cases checking whether a graph is in a given minor closed family can be done more efficiently for example checking whether a graph is planar can be done in linear time Fixed parameter tractability EditFor graph invariants with the property that for each k the graphs with invariant at most k are minor closed the same method applies For instance by this result treewidth branchwidth and pathwidth vertex cover and the minimum genus of an embedding are all amenable to this approach and for any fixed k there is a polynomial time algorithm for testing whether these invariants are at most k in which the exponent in the running time of the algorithm does not depend on k A problem with this property that it can be solved in polynomial time for any fixed k with an exponent that does not depend on k is known as fixed parameter tractable However this method does not directly provide a single fixed parameter tractable algorithm for computing the parameter value for a given graph with unknown k because of the difficulty of determining the set of forbidden minors Additionally the large constant factors involved in these results make them highly impractical Therefore the development of explicit fixed parameter algorithms for these problems with improved dependence on k has continued to be an important line of research Finite form of the graph minor theorem EditFriedman Robertson amp Seymour 1987 showed that the following theorem exhibits the independence phenomenon by being unprovable in various formal systems that are much stronger than Peano arithmetic yet being provable in systems much weaker than ZFC Theorem For every positive integer n there is an integer m so large that if G1 Gm is a sequence of finite undirected graphs where each Gi has size at most n i then Gj Gk for some j lt k Here the size of a graph is the total number of its vertices and edges and denotes the minor ordering See also EditGraph structure theoremNotes Edit Bienstock amp Langston 1995 Robertson amp Seymour 2004 Robertson and Seymour 1983 2004 Diestel 2005 p 333 Diestel 2005 p 355 Diestel 2005 pp 335 336 Lovasz 2005 Section 3 3 pp 78 79 E g see Bienstock amp Langston 1995 Section 2 well quasi orders Diestel 2005 p 334 a b Lovasz 2005 p 78 Bienstock amp Langston 1995 Corollary 2 1 1 Lovasz 2005 Theorem 4 p 78 a b Lovasz 2005 pp 76 77 Myrvold amp Woodcock 2018 Kawarabayashi Kobayashi amp Reed 2012 Robertson amp Seymour 1995 Bienstock amp Langston 1995 Theorem 2 1 4 and Corollary 2 1 5 Lovasz 2005 Theorem 11 p 83 Fellows amp Langston 1988 Bienstock amp Langston 1995 Section 6 References EditBienstock Daniel Langston Michael A 1995 Algorithmic implications of the graph minor theorem PDF Network Models Handbooks in Operations Research and Management Science vol 7 pp 481 502 doi 10 1016 S0927 0507 05 80125 2 Diestel Reinhard 2005 Minors Trees and WQO Graph Theory PDF Electronic Edition 2005 ed Springer pp 326 367 Fellows Michael R Langston Michael A 1988 Nonconstructive tools for proving polynomial time decidability Journal of the ACM 35 3 727 739 doi 10 1145 44483 44491 Friedman Harvey Robertson Neil Seymour Paul 1987 The metamathematics of the graph minor theorem in Simpson S ed Logic and Combinatorics Contemporary Mathematics vol 65 American Mathematical Society pp 229 261 Kawarabayashi Ken ichi Kobayashi Yusuke Reed Bruce 2012 The disjoint paths problem in quadratic time PDF Journal of Combinatorial Theory Series B 102 2 424 435 doi 10 1016 j jctb 2011 07 004 Lovasz Laszlo 2005 Graph Minor Theory Bulletin of the American Mathematical Society New Series 43 1 75 86 doi 10 1090 S0273 0979 05 01088 8 Myrvold Wendy Woodcock Jennifer 2018 A Large Set of Torus Obstructions and How They Were Discovered The Electronic Journal of Combinatorics 25 1 P1 16 doi 10 37236 3797 Robertson Neil Seymour Paul 1983 Graph Minors I Excluding a forest Journal of Combinatorial Theory Series B 35 1 39 61 doi 10 1016 0095 8956 83 90079 5 Robertson Neil Seymour Paul 1995 Graph Minors XIII The disjoint paths problem Journal of Combinatorial Theory Series B 63 1 65 110 doi 10 1006 jctb 1995 1006 Robertson Neil Seymour Paul 2004 Graph Minors XX Wagner s conjecture Journal of Combinatorial Theory Series B 92 2 325 357 doi 10 1016 j jctb 2004 08 001 External links EditWeisstein Eric W Robertson Seymour Theorem MathWorld Retrieved from https en wikipedia org w index php title Robertson Seymour theorem amp oldid 1132804889, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.