287:
273:
265:
1284:. Shallow minors interpolate between the theories of graph minors and subgraphs, in that shallow minors with high depth coincide with the usual type of graph minor, while the shallow minors with depth zero are exactly the subgraphs. They also allow the theory of graph minors to be extended to classes of graphs such as the
1081:
The topological minor relation is not a well-quasi-ordering on the set of finite graphs and hence the result of
Robertson and Seymour does not apply to topological minors. However it is straightforward to construct finite forbidden topological minor characterizations from finite forbidden minor
1260:: from a drawing of a graph in the plane, with crossings, one can form an immersion minor by replacing each crossing point by a new vertex, and in the process also subdividing each crossed edge into a path. This allows drawing methods for planar graphs to be extended to non-planar graphs.
1244:
The immersion minor relation is a well-quasi-ordering on the set of finite graphs and hence the result of
Robertson and Seymour applies to immersion minors. This furthermore means that every immersion minor-closed family is characterized by a finite family of forbidden immersion minors.
209:) it makes more sense to allow the deletion of a cut-edge, and to allow disconnected graphs, but to forbid multigraphs. In this variation of graph minor theory, a graph is always simplified after any edge contraction to eliminate its self-loops and multiple edges.
1647:
is inconsistent about whether to allow self-loops and multiple adjacencies: he writes on p. 76 that "parallel edges and loops are allowed" but on p. 77 he states that "a graph is a forest if and only if it does not contain the triangle
1352:
that represents an adjacency between two subtrees is monochromatic (both its endpoints are the same color). Unlike for the usual kind of graph minors, graphs with forbidden odd minors are not necessarily sparse. The
1518:) time. Thus, by applying the polynomial time algorithm for testing whether a given graph contains any of the forbidden minors, it is theoretically possible to recognize the members of any minor-closed family in
1530:. Furthermore, in order to apply this result constructively, it is necessary to know what the forbidden minors of the graph family are. In some cases, the forbidden minors are known, or can be computed.
3233:
502:
615:
568:
739:
674:
920:
In some cases, the properties of the graphs in a minor-closed family may be closely connected to the properties of their excluded minors. For example a minor-closed graph family
113:; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.
167:
by contracting some edges, deleting some edges, and deleting some isolated vertices. The order in which a sequence of such contractions and deletions is performed on
980:-minor-free graphs have a simplified structure theorem in which they are formed as clique-sums of planar graphs and graphs of bounded treewidth. For instance, both
2791:
2689:
2313:
2466:; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2002), "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor",
410:
as a minor. The statement of the theorem is itself long and involved, but in short it establishes that such a graph must have the structure of a
2867:
2493:
144:
An edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices it used to connect. An
282:
by deleting the dashed edges (and the resulting isolated vertex), and then contract the gray edge (merging the two vertices it connects):
1354:
797:
call it "one of the deepest unsolved problems in graph theory." Another result relating the four-color theorem to graph minors is the
745:
125:
2388:
878:
3272:
3127:
3097:
3065:
3013:
2981:
2721:
2505:
2090:
2036:
869:
is a minor-closed family, then (because of the well-quasi-ordering property of minors) among the graphs that do not belong to
3150:
3118:
3088:
3056:
3035:
3004:
2972:
973:
330:
829:
441:, which means that the number of edges is less than some constant multiple of the number of vertices. More specifically, if
325:
can only be minors of each other if they are isomorphic because any nontrivial minor operation removes edges or vertices. A
90:
3385:
3047:
3206:
3158:
3154:
3122:
3092:
3060:
3039:
3008:
2976:
2308:
2304:
2085:
2027:
1523:
1396:
by deleting vertices, deleting edges, and collapsing pairs of vertices that are at distance two from each other along a
460:
334:
576:
529:
3380:
862:
of the embedding; therefore, planar graphs and the graphs embeddable on any fixed surface form minor-closed families.
286:
1217:. There is yet another way of defining immersion minors, which is equivalent to the lifting operation. We say that
2940:
2936:
2924:
Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Shallow excluded minors and improved graph decompositions",
2716:
2023:
1985:
1045:
2220:
2193:
709:
644:
571:
1194:
will now be connected by more than one edge, and hence this operation is intrinsically a multi-graph operation.
97:
exists for every property of graphs that is preserved by deletions and edge contractions. For every fixed graph
2847:
1057:
801:
announced by
Robertson, Sanders, Seymour, and Thomas, a strengthening of the four-color theorem conjectured by
622:
78:
2743:
Kostochka, Alexandr V. (1982), "The minimum
Hadwiger number for graphs with a given mean degree of vertices",
2843:
1281:
961:
399:
117:
3218:, London Math. Soc. Lecture Note Ser., vol. 267, Cambridge: Cambridge Univ. Press, pp. 201–222,
2712:
2164:
1981:
136:
as a minor of it. Important variants of graph minors include the topological minors and immersion minors.
2786:
2468:
Proc. 5th
International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002)
1064:. Every topological minor is also a minor. The converse however is not true in general (for instance the
806:
524:
47:
2757:
Kostochka, Alexandr V. (1984), "Lower bound of the
Hadwiger number of graphs by their average degree",
1478:
is fixed, it can be solved in polynomial time. More specifically, the running time for testing whether
1078:
is a minor but not a topological one), but holds for graph with maximum degree not greater than three.
391:
under the minor ordering. This result proved a conjecture formerly known as Wagner's conjecture, after
3242:
2904:
2367:
1522:. This result is not used in practice since the hidden constant is so huge (needing three layers of
1373:
2169:
387:. Another equivalent way of stating this is that any set of graphs can have only a finite number of
1401:
929:
906:
859:
419:
338:
306:
199:
183:
58:
2483:
2379:
2246:
Adler, Isolde; Dorn, Frederic; Fomin, Fedor V.; Sau, Ignasi; Thilikos, Dimitrios M. (2012-09-01).
272:
264:
3315:
3258:
3194:
2960:
2831:
2774:
2658:
2640:
2614:
2595:
2574:
2548:
2451:
2357:
2332:
2278:
2125:
2099:
2001:
1527:
783:
2431:
1321:
3353:
2863:
2489:
2270:
1467:
1053:
156:
198:
are forbidden operations. This point of view has the advantage that edge deletions leave the
3307:
3281:
3250:
3186:
3136:
3106:
3074:
3022:
2990:
2952:
2912:
2855:
2823:
2800:
2766:
2730:
2698:
2650:
2604:
2590:
2558:
2514:
2471:
2443:
2414:
2397:
2322:
2262:
2174:
2109:
2073:
2045:
1993:
1431:
1397:
1348:
within a subtree is properly colored (its endpoints have different colors) and each edge of
145:
94:
51:
24:
3223:
3044:
Graph
Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
2877:
2570:
2528:
2344:
2121:
2059:
3219:
2873:
2814:
Mader, Wolfgang (1967), "Homomorphieeigenschaften und mittlere
Kantendichte von Graphen",
2586:
2566:
2524:
2340:
2117:
2055:
1519:
1377:
851:
423:
415:
388:
298:
110:
3042:(1993), "Excluding a graph with one crossing", in Robertson, Neil; Seymour, Paul (eds.),
3246:
2908:
2371:
1280:
that were contracted to form the minor form a collection of disjoint subgraphs with low
2536:
2155:
Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)".
2081:
1503:
1366:
1285:
1075:
1065:
817:
765:
753:
133:
129:
66:
3162:
3110:
2470:, Lecture Notes in Computer Science, vol. 2462, Springer-Verlag, pp. 67–80,
2401:
2352:
Błasiok, Jarosław; Kamiński, Marcin; Raymond, Jean-Florent; Trunck, Théophile (2015),
3374:
3319:
3262:
3177:
3027:
2995:
2835:
2670:
2631:
2383:
2178:
1413:
1372:
A different parity-based extension of the notion of graph minors is the concept of a
1269:
1253:
1249:
813:
798:
302:
187:
179:
3210:
2943:(2009), "A linear-time algorithm to find a separator in a graph excluding a minor",
2778:
2703:
2662:
2618:
2129:
2005:
3327:
3295:
3198:
2885:
2626:
2578:
2463:
2427:
2421:, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL
2410:
2282:
1538:
1409:
1257:
1002:
953:
847:
438:
392:
206:
62:
20:
2964:
2889:
2805:
2455:
905:
of forbidden minors. The best-known example of a characterization of this type is
828:
Further information on minor-closed graph families, including a list of some:
422:. Thus, their theory establishes fundamental connections between graph minors and
2247:
1001:-free graphs are exactly the 3-clique-sums of planar graphs and the eight-vertex
3356:
1447:
809:
802:
326:
3141:
2735:
2113:
2050:
3254:
2925:
2859:
2654:
2447:
2266:
2019:
1510:; since the original Graph Minors result, this algorithm has been improved to
965:
941:
937:
855:
411:
191:
182:. In this context, it is common to assume that all graphs are connected, with
2916:
2274:
858:, neither the removal of edges nor the contraction of edges can increase the
3361:
3231:
Thomason, Andrew (1984), "An extremal function for contractions of graphs",
2956:
2475:
2300:
2077:
1324:
restricts this definition by adding parity conditions to these subtrees. If
1316:, there exists an edge with its endpoints in the corresponding two trees in
949:
925:
704:
194:
rather than simple graphs); the contraction of a loop and the deletion of a
3286:
3079:
2629:(2003), "Local tree-width, excluded minors, and approximation algorithms",
2519:
2409:
Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; JĂĽnger, Michael;
1988:; Wollan, Paul (2011), "The graph minor algorithm with parity conditions",
202:
of a graph unchanged, and edge contractions always reduce the rank by one.
2593:(1988), "Nonconstructive tools for proving polynomial-time decidability",
2562:
1997:
834:
Many families of graphs have the property that every minor of a graph in
395:; Wagner had conjectured it long earlier, but only published it in 1970.
342:
195:
2854:, Algorithms and Combinatorics, vol. 28, Springer, pp. 62–65,
2609:
2553:
968:(a graph that can be made planar by the removal of a single vertex). If
3311:
3190:
2827:
2770:
2336:
1369:
as minors, has also been studied from the point of view of odd minors.
972:
can be drawn in the plane with only a single crossing (that is, it has
3270:
Thomason, Andrew (2001), "The extremal function for complete minors",
278:
The following diagram illustrates this. First construct a subgraph of
2645:
1992:, Institute of Electrical and Electronics Engineers, pp. 27–36,
1012:-free graphs are exactly the 2-clique-sums of planar graphs and
2327:
2362:
398:
In the course of their proof, Seymour and
Robertson also prove the
2432:"Diameter and treewidth in minor-closed graph families, revisited"
2104:
1308:
can be represented by a collection of vertex-disjoint subtrees of
1296:
An alternative and equivalent definition of a graph minor is that
2539:(2000), "Diameter and treewidth in minor-closed graph families",
116:
Other results and conjectures involving graph minors include the
2386:(1980), "Hadwiger's conjecture is true for almost every graph",
1340:
whenever it is possible to assign two colors to the vertices of
940:
if and only if its forbidden minors include a disjoint union of
124:
as a minor may be formed by gluing together simpler pieces, and
3234:
Mathematical
Proceedings of the Cambridge Philosophical Society
960:
has bounded local treewidth (a functional relationship between
909:
characterizing the planar graphs as the graphs having neither K
363:
of finite graphs is given, then there always exist two indices
2719:(March 2012), "The disjoint paths problem in quadratic time",
2031:
1944:
964:
and treewidth) if and only if its forbidden minors include an
414:
of smaller graphs that are modified in small ways from graphs
305:
on the isomorphism classes of finite undirected graphs: it is
178:
Graph minors are often studied in the more general context of
1990:
52nd Annual IEEE Symposium on Foundations of Computer Science
3330:(1937b), "Ăśber eine Erweiterung des Satzes von Kuratowski",
1933:
1557:
is not fixed, faster algorithms are known in the case where
3095:(2003), "Graph Minors. XVI. Excluding a non-planar graph",
2927:
Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994)
2687:
Hall, Dick Wick (1943), "A note on primitive skew curves",
889:
if and only if it does not contain as a minor any graph in
621:-minor-free graphs have a separator theorem similar to the
511:-minor-free graphs have at least this many edges. Thus, if
3063:(1995), "Graph Minors. XIII. The disjoint paths problem",
2503:
Ding, Guoli (1996), "Excluding a long double path minor",
2142:
2673:(1943), "Ăśber eine Klassifikation der Streckenkomplexe",
1865:
1142:
is an operation on adjacent edges. Given three vertices
1968:
1956:
1526:
to express) as to rule out any application, making it a
680:
into two (possibly disconnected) subgraphs with at most
1442:
as a minor is NP-complete in general; for instance, if
1209:) and then finding an isomorphic subgraph, we say that
3298:(1937a), "Ăśber eine Eigenschaft der ebenen Komplexe",
1789:
1225:
if there exists an injective mapping from vertices in
713:
648:
580:
533:
464:
406:, the rough structure of any graph that does not have
3209:(1999), "Recent excluded minor theorems for graphs",
3011:(1986), "Graph minors. V. Excluding a planar graph",
1082:
characterizations by replacing every branch set with
712:
647:
579:
532:
463:
297:
It is straightforward to verify that the graph minor
2311:(1990), "A separator theorem for nonplanar graphs",
1541:, then we can test in linear time in an input graph
1506:
hides a constant that depends superexponentially on
994:have crossing number one, and as Wagner showed the
695:
vertices per subgraph. Even stronger, for any fixed
2488:(3rd ed.), Berlin, New York: Springer-Verlag,
2032:"On the odd-minor variant of Hadwiger's conjecture"
794:
1380:whenever the starting graph is bipartite. A graph
1110:if it can be obtained from an induced subgraph of
733:
668:
609:
562:
497:{\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}
496:
3125:(2004), "Graph Minors. XX. Wagner's conjecture",
1849:
1746:
610:{\displaystyle \scriptstyle O(h{\sqrt {\log h}})}
563:{\displaystyle \scriptstyle O(h{\sqrt {\log h}})}
120:, according to which the graphs that do not have
1861:
1833:
1817:
1698:
1670:
1617:
1602:
1404:applies for bipartite minors: A bipartite graph
216:is referred to as "minor-monotone" if, whenever
2979:(1983), "Graph minors. I. Excluding a forest",
2890:"Book Review: The Colossal Book of Mathematics"
1750:
1632:
1328:is represented by a collection of subtrees of
952:if and only if its forbidden minors include a
928:if and only if its forbidden minors include a
786:. The Hadwiger conjecture has been proven for
65:if and only if its minors include neither the
2792:Bulletin of the American Mathematical Society
2690:Bulletin of the American Mathematical Society
402:in which they determine, for any fixed graph
337:states that this partial order is actually a
205:In other contexts (such as with the study of
8:
2897:Notices of the American Mathematical Society
2852:Sparsity: Graphs, Structures, and Algorithms
2314:Journal of the American Mathematical Society
1312:, such that if two vertices are adjacent in
1170:is the operation that deletes the two edges
3212:Surveys in combinatorics, 1999 (Canterbury)
3046:, Contemporary Mathematics, vol. 147,
2419:Handbook of Graph Drawing and Visualization
752:does not contain a minor isomorphic to the
734:{\displaystyle \scriptstyle O({\sqrt {n}})}
669:{\displaystyle \scriptstyle O({\sqrt {n}})}
2413:(2014), "Crossings and planarization", in
2143:Kawarabayashi, Kobayashi & Reed (2012)
1090:leaves that has down degree at least two.
877:of minor-minimal graphs. These graphs are
3285:
3273:Journal of Combinatorial Theory, Series B
3140:
3128:Journal of Combinatorial Theory, Series B
3098:Journal of Combinatorial Theory, Series B
3078:
3066:Journal of Combinatorial Theory, Series B
3026:
3014:Journal of Combinatorial Theory, Series B
2994:
2982:Journal of Combinatorial Theory, Series B
2804:
2734:
2722:Journal of Combinatorial Theory, Series B
2702:
2644:
2608:
2552:
2518:
2361:
2326:
2168:
2103:
2049:
1866:Demaine, Hajiaghayi & Thilikos (2002)
1726:
1722:
1657:as a minor", true only for simple graphs.
1288:that are not closed under taking minors.
1233:where the images of adjacent elements of
748:in graph theory proposes that if a graph
720:
711:
655:
646:
590:
578:
543:
531:
477:
462:
1845:
1777:
1754:
1734:
1730:
1205:by a sequence of lifting operations (on
1909:
1897:
1881:
1877:
1666:
1583:
1569:
1162:are edges in the graph, the lifting of
901:-minor-free graphs for some finite set
151:is a minor of another undirected graph
2675:Vierteljschr. Naturforsch. Ges. ZĂĽrich
2354:Induced minors and well-quasi-ordering
1969:Nešetřil & Ossona de Mendez (2012)
1957:Nešetřil & Ossona de Mendez (2012)
1829:
1801:
1790:Robertson, Seymour & Thomas (1993)
1694:
1682:
1669:, Chapter 12: Minors, Trees, and WQO;
1644:
1628:
1626:
1613:
1611:
1598:
1579:
1384:is a bipartite minor of another graph
1361:-chromatic graphs necessarily contain
897:can be characterized as the family of
793:, but is unknown in the general case.
57:The theory of graph minors began with
2248:"Fast Minor Testing in Planar Graphs"
1766:
1710:
1594:
1592:
893:. That is, every minor-closed family
641:, it is possible to find a subset of
7:
2430:; Hajiaghayi, MohammadTaghi (2004),
1921:
1885:
1805:
1450:with the same number of vertices as
1412:if and only if it does not have the
171:does not affect the resulting graph
2221:"A Tourist Guide through Treewidth"
2194:"A Tourist Guide through Treewidth"
1575:
1573:
795:Bollobás, Catlin & Erdős (1980)
457:-minor-free graph can have at most
14:
2389:European Journal of Combinatorics
2236:First paragraph after Theorem 5.3
1747:Alon, Seymour & Thomas (1990)
1276:is a minor in which the edges of
1114:by contracting edges. Otherwise,
625:for planar graphs: for any fixed
101:, it is possible to test whether
1344:in such a way that each edge of
1252:, immersion minors arise as the
1086:outgoing edges by every tree on
812:that requires four colors in an
523:-minor-free graphs have average
285:
271:
263:
251:In the following example, graph
95:forbidden minor characterization
2704:10.1090/S0002-9904-1943-08065-2
2506:Journal of Combinatorial Theory
2091:Journal of Combinatorial Theory
2037:Journal of Combinatorial Theory
1850:Demaine & Hajiaghayi (2004)
1751:Plotkin, Rao & Smith (1994)
1134:is central in a concept called
2945:ACM Transactions on Algorithms
2789:(2006), "Graph minor theory",
1862:Robertson & Seymour (1993)
1834:Robertson & Seymour (1986)
1818:Robertson & Seymour (1983)
1699:Robertson & Seymour (2003)
1671:Robertson & Seymour (2004)
1618:Robertson & Seymour (1995)
1603:Robertson & Seymour (2004)
727:
717:
676:vertices whose removal splits
662:
652:
603:
584:
556:
537:
490:
468:
16:Subgraph with contracted edges
1:
3111:10.1016/S0095-8956(03)00042-X
3048:American Mathematical Society
2806:10.1090/S0273-0979-05-01088-8
2402:10.1016/s0195-6698(80)80001-1
1633:Fellows & Langston (1988)
1498:is the number of vertices in
1201:can be obtained from a graph
842:; such a class is said to be
293:Major results and conjectures
105:is a minor of an input graph
3028:10.1016/0095-8956(86)90030-4
2996:10.1016/0095-8956(83)90079-5
2219:Bodlaender, Hans L. (1993).
2192:Bodlaender, Hans L. (1993).
2179:10.1016/0196-6774(87)90043-5
2088:(2016), "Bipartite minors",
132:to the existence of a large
3163:"Hadwiger's conjecture for
824:Minor-closed graph families
437:-minor-free graphs must be
190:allowed (that is, they are
3402:
3142:10.1016/j.jctb.2004.08.001
2736:10.1016/j.jctb.2011.07.004
2482:Diestel, Reinhard (2005),
2114:10.1016/j.jctb.2015.08.001
2051:10.1016/j.jctb.2008.03.006
1197:In the case where a graph
827:
128:relating the inability to
93:implies that an analogous
3255:10.1017/S0305004100061521
2860:10.1007/978-3-642-27875-4
2848:Ossona de Mendez, Patrice
2655:10.1007/s00493-003-0037-9
2448:10.1007/s00453-004-1106-1
2267:10.1007/s00453-011-9563-9
1832:, Theorem 9, p. 81;
1601:, theorem 4, p. 78;
1524:Knuth's up-arrow notation
1474:is part of the input but
1304:whenever the vertices of
1221:is an immersion minor of
1213:is an immersion minor of
1130:A graph operation called
830:Robertson–Seymour theorem
91:Robertson–Seymour theorem
2917:10.1109/TED.2002.1003756
2030:; Vetta, Adrian (2009),
1400:of the graph. A form of
1241:by edge-disjoint paths.
782:is a restatement of the
703:-minor-free graphs have
623:planar separator theorem
449:vertices, then a simple
79:complete bipartite graph
2957:10.1145/1597036.1597043
2745:Metody Diskret. Analiz.
2713:Kawarabayashi, Ken-ichi
2476:10.1007/3-540-45753-4_8
1982:Kawarabayashi, Ken-ichi
846:. For instance, in any
418:on surfaces of bounded
400:graph structure theorem
309:(a minor of a minor of
118:graph structure theorem
3287:10.1006/jctb.2000.2013
3080:10.1006/jctb.1995.1006
2520:10.1006/jctb.1996.0002
1945:Buchheim et al. (2014)
1755:Reed & Wood (2009)
1422:as a bipartite minor.
873:there is a finite set
854:of a graph on a fixed
735:
670:
611:
564:
498:
424:topological embeddings
2816:Mathematische Annalen
2715:; Kobayashi, Yusuke;
2563:10.1007/s004530010020
2209:See end of Section 5.
2157:Journal of Algorithms
1934:BĹ‚asiok et al. (2015)
1392:can be obtained from
1186:already was present,
1182:. In the case where
1122:-induced minor-free.
885:: a graph belongs to
805:and stating that any
736:
671:
612:
565:
499:
163:can be obtained from
126:Hadwiger's conjecture
3386:Graph theory objects
2591:Langston, Michael A.
1998:10.1109/focs.2011.52
710:
645:
617:. Additionally, the
577:
530:
461:
255:is a minor of graph
3332:Deutsche Mathematik
3247:1983MPCPS..95..261T
2909:2002ITED...49.1084A
2610:10.1145/44483.44491
2587:Fellows, Michael R.
2372:2015arXiv151007135B
1376:, which produces a
1355:Hadwiger conjecture
1336:is an odd minor of
1166:, or equivalent of
856:topological surface
746:Hadwiger conjecture
339:well-quasi-ordering
46:by deleting edges,
42:can be formed from
3381:Graph minor theory
3354:Weisstein, Eric W.
3312:10.1007/BF01594196
3191:10.1007/BF01202354
3050:, pp. 669–675
2930:, pp. 462–470
2844:Nešetřil, Jaroslav
2828:10.1007/BF01364272
2771:10.1007/BF02579141
2596:Journal of the ACM
1533:In the case where
1528:galactic algorithm
1178:and adds the edge
1028:Topological minors
784:four color theorem
731:
730:
666:
665:
637:-minor-free graph
607:
606:
560:
559:
494:
493:
2951:(4): Article 39,
2869:978-3-642-27874-7
2495:978-3-540-26183-4
2415:Tamassia, Roberto
2382:; Catlin, P. A.;
2074:Chudnovsky, Maria
2022:; Gerards, Bert;
1553:. In cases where
1468:Hamiltonian cycle
1292:Parity conditions
1258:non-planar graphs
1237:are connected in
1038:topological minor
775:colors. The case
725:
660:
601:
554:
488:
52:contracting edges
3393:
3367:
3366:
3339:
3322:
3290:
3289:
3265:
3226:
3217:
3201:
3174:
3145:
3144:
3123:Seymour, Paul D.
3113:
3093:Seymour, Paul D.
3083:
3082:
3061:Seymour, Paul D.
3051:
3040:Seymour, Paul D.
3031:
3030:
3009:Seymour, Paul D.
2999:
2998:
2967:
2931:
2919:
2903:(9): 1084–1086,
2894:
2880:
2838:
2809:
2808:
2781:
2752:
2739:
2738:
2707:
2706:
2682:
2665:
2648:
2621:
2612:
2581:
2556:
2531:
2522:
2498:
2478:
2464:Demaine, Erik D.
2458:
2428:Demaine, Erik D.
2422:
2404:
2374:
2365:
2347:
2330:
2287:
2286:
2252:
2243:
2237:
2235:
2228:Acta Cybernetica
2225:
2216:
2210:
2208:
2201:Acta Cybernetica
2198:
2189:
2183:
2182:
2172:
2152:
2146:
2140:
2134:
2132:
2107:
2070:
2064:
2062:
2053:
2016:
2010:
2008:
1978:
1972:
1966:
1960:
1954:
1948:
1942:
1936:
1931:
1925:
1919:
1913:
1907:
1901:
1895:
1889:
1875:
1869:
1859:
1853:
1843:
1837:
1827:
1821:
1815:
1809:
1799:
1793:
1787:
1781:
1775:
1769:
1764:
1758:
1744:
1738:
1727:Kostochka (1984)
1723:Kostochka (1982)
1720:
1714:
1708:
1702:
1692:
1686:
1680:
1674:
1664:
1658:
1656:
1642:
1636:
1630:
1621:
1615:
1606:
1596:
1587:
1577:
1486:in this case is
1470:. However, when
1434:whether a graph
1402:Wagner's theorem
1398:peripheral cycle
907:Wagner's theorem
879:forbidden minors
792:
781:
774:
763:
759:
751:
740:
738:
737:
732:
726:
721:
702:
698:
694:
693:
692:
688:
679:
675:
673:
672:
667:
661:
656:
640:
636:
632:
628:
620:
616:
614:
613:
608:
602:
591:
570:and furthermore
569:
567:
566:
561:
555:
544:
522:
518:
514:
510:
504:edges, and some
503:
501:
500:
495:
489:
478:
456:
452:
448:
444:
436:
432:
409:
405:
389:minimal elements
386:
379:
372:
362:
324:
320:
316:
312:
289:
275:
267:
242:
223:
219:
215:
174:
170:
166:
162:
157:graph isomorphic
154:
150:
146:undirected graph
123:
108:
104:
100:
88:
76:
61:that a graph is
59:Wagner's theorem
45:
41:
37:
29:
25:undirected graph
3401:
3400:
3396:
3395:
3394:
3392:
3391:
3390:
3371:
3370:
3352:
3351:
3348:
3343:
3326:
3294:
3269:
3230:
3215:
3205:
3172:
3169:
3151:Robertson, Neil
3149:
3119:Robertson, Neil
3117:
3089:Robertson, Neil
3087:
3057:Robertson, Neil
3055:
3036:Robertson, Neil
3034:
3005:Robertson, Neil
3003:
2973:Robertson, Neil
2971:
2935:
2923:
2892:
2884:
2870:
2842:
2813:
2785:
2756:
2742:
2711:
2697:(12): 935–936,
2686:
2669:
2625:
2585:
2554:math.CO/9907126
2537:Eppstein, David
2535:
2502:
2496:
2481:
2462:
2426:
2408:
2378:
2351:
2328:10.2307/1990903
2299:
2295:
2290:
2250:
2245:
2244:
2240:
2223:
2218:
2217:
2213:
2196:
2191:
2190:
2186:
2170:10.1.1.114.3864
2154:
2153:
2149:
2141:
2137:
2082:Novik, Isabella
2072:
2071:
2067:
2018:
2017:
2013:
1980:
1979:
1975:
1967:
1963:
1955:
1951:
1943:
1939:
1932:
1928:
1920:
1916:
1908:
1904:
1896:
1892:
1876:
1872:
1860:
1856:
1846:Eppstein (2000)
1844:
1840:
1828:
1824:
1816:
1812:
1800:
1796:
1788:
1784:
1778:Hadwiger (1943)
1776:
1772:
1765:
1761:
1745:
1741:
1735:Thomason (2001)
1731:Thomason (1984)
1721:
1717:
1709:
1705:
1693:
1689:
1681:
1677:
1665:
1661:
1655:
1649:
1643:
1639:
1631:
1624:
1616:
1609:
1597:
1590:
1578:
1571:
1567:
1520:polynomial time
1462:if and only if
1430:The problem of
1428:
1421:
1378:bipartite graph
1374:bipartite minor
1367:complete graphs
1332:as above, then
1294:
1286:1-planar graphs
1266:
1229:to vertices in
1128:
1126:Immersion minor
1096:
1073:
1030:
1025:
1018:
1011:
1000:
993:
986:
974:crossing number
916:
912:
832:
826:
810:3-regular graph
787:
776:
769:
766:proper coloring
761:
760:vertices, then
757:
749:
708:
707:
700:
696:
690:
683:
682:
681:
677:
643:
642:
638:
634:
630:
626:
618:
575:
574:
528:
527:
520:
519:vertices, then
516:
512:
509:
505:
459:
458:
454:
453:-vertex simple
450:
446:
442:
434:
430:
407:
403:
385:
381:
378:
374:
364:
360:
353:
346:
322:
318:
314:
310:
295:
249:
225:
221:
217:
213:
172:
168:
164:
160:
152:
148:
142:
121:
111:polynomial time
106:
102:
98:
87:
81:
75:
69:
43:
39:
35:
27:
17:
12:
11:
5:
3399:
3397:
3389:
3388:
3383:
3373:
3372:
3369:
3368:
3347:
3346:External links
3344:
3342:
3341:
3324:
3292:
3280:(2): 318–338,
3267:
3241:(2): 261–265,
3228:
3203:
3185:(3): 279–361,
3167:
3147:
3135:(2): 325–357,
3115:
3085:
3053:
3032:
3001:
2969:
2941:Wood, David R.
2933:
2921:
2882:
2868:
2840:
2822:(4): 265–268,
2811:
2787:Lovász, László
2783:
2765:(4): 307–316,
2754:
2747:(in Russian),
2740:
2729:(2): 424–435,
2709:
2684:
2671:Hadwiger, Hugo
2667:
2639:(4): 613–632,
2623:
2603:(3): 727–739,
2583:
2547:(3): 275–291,
2533:
2500:
2494:
2479:
2460:
2442:(3): 211–215,
2424:
2406:
2396:(3): 195–199,
2376:
2349:
2321:(4): 801–808,
2296:
2294:
2291:
2289:
2288:
2238:
2211:
2184:
2163:(2): 285–303.
2147:
2135:
2080:; Nevo, Eran;
2065:
2011:
1973:
1971:, pp. 319–321.
1961:
1949:
1937:
1926:
1914:
1902:
1890:
1882:Wagner (1937b)
1878:Wagner (1937a)
1870:
1854:
1838:
1822:
1810:
1794:
1782:
1770:
1759:
1739:
1715:
1703:
1687:
1675:
1667:Diestel (2005)
1659:
1653:
1637:
1622:
1607:
1588:
1584:Wagner (1937a)
1582:, p. 77;
1568:
1566:
1563:
1549:is a minor of
1504:big O notation
1482:is a minor of
1458:is a minor of
1427:
1424:
1419:
1300:is a minor of
1293:
1290:
1265:
1264:Shallow minors
1262:
1254:planarizations
1127:
1124:
1118:is said to be
1095:
1094:Induced minors
1092:
1076:Petersen graph
1071:
1066:complete graph
1029:
1026:
1024:
1021:
1016:
1009:
998:
991:
984:
976:one) then the
914:
910:
825:
822:
818:Petersen graph
816:must have the
754:complete graph
729:
724:
719:
716:
664:
659:
654:
651:
605:
600:
597:
594:
589:
586:
583:
558:
553:
550:
547:
542:
539:
536:
507:
492:
487:
484:
481:
476:
473:
470:
467:
429:For any graph
383:
380:is a minor of
376:
358:
351:
331:Neil Robertson
313:is a minor of
294:
291:
248:
245:
220:is a minor of
188:multiple edges
180:matroid minors
141:
138:
134:complete graph
85:
73:
67:complete graph
15:
13:
10:
9:
6:
4:
3:
2:
3398:
3387:
3384:
3382:
3379:
3378:
3376:
3364:
3363:
3358:
3357:"Graph Minor"
3355:
3350:
3349:
3345:
3337:
3333:
3329:
3328:Wagner, Klaus
3325:
3321:
3317:
3313:
3309:
3305:
3301:
3297:
3296:Wagner, Klaus
3293:
3288:
3283:
3279:
3275:
3274:
3268:
3264:
3260:
3256:
3252:
3248:
3244:
3240:
3236:
3235:
3229:
3225:
3221:
3214:
3213:
3208:
3207:Thomas, Robin
3204:
3200:
3196:
3192:
3188:
3184:
3180:
3179:
3178:Combinatorica
3171:
3170:-free graphs"
3166:
3160:
3159:Thomas, Robin
3156:
3155:Seymour, Paul
3152:
3148:
3143:
3138:
3134:
3130:
3129:
3124:
3120:
3116:
3112:
3108:
3104:
3100:
3099:
3094:
3090:
3086:
3081:
3076:
3073:(1): 65–110,
3072:
3068:
3067:
3062:
3058:
3054:
3049:
3045:
3041:
3037:
3033:
3029:
3024:
3021:(1): 92–114,
3020:
3016:
3015:
3010:
3006:
3002:
2997:
2992:
2988:
2984:
2983:
2978:
2977:Seymour, Paul
2974:
2970:
2966:
2962:
2958:
2954:
2950:
2946:
2942:
2938:
2934:
2929:
2928:
2922:
2918:
2914:
2910:
2906:
2902:
2898:
2891:
2887:
2883:
2879:
2875:
2871:
2865:
2861:
2857:
2853:
2849:
2845:
2841:
2837:
2833:
2829:
2825:
2821:
2817:
2812:
2807:
2802:
2798:
2794:
2793:
2788:
2784:
2780:
2776:
2772:
2768:
2764:
2760:
2759:Combinatorica
2755:
2750:
2746:
2741:
2737:
2732:
2728:
2724:
2723:
2718:
2714:
2710:
2705:
2700:
2696:
2692:
2691:
2685:
2680:
2676:
2672:
2668:
2664:
2660:
2656:
2652:
2647:
2642:
2638:
2634:
2633:
2632:Combinatorica
2628:
2627:Grohe, Martin
2624:
2620:
2616:
2611:
2606:
2602:
2598:
2597:
2592:
2588:
2584:
2580:
2576:
2572:
2568:
2564:
2560:
2555:
2550:
2546:
2542:
2538:
2534:
2530:
2526:
2521:
2516:
2512:
2508:
2507:
2501:
2497:
2491:
2487:
2486:
2480:
2477:
2473:
2469:
2465:
2461:
2457:
2453:
2449:
2445:
2441:
2437:
2433:
2429:
2425:
2420:
2416:
2412:
2411:Mutzel, Petra
2407:
2403:
2399:
2395:
2391:
2390:
2385:
2381:
2377:
2373:
2369:
2364:
2359:
2355:
2350:
2346:
2342:
2338:
2334:
2329:
2324:
2320:
2316:
2315:
2310:
2309:Thomas, Robin
2306:
2305:Seymour, Paul
2302:
2298:
2297:
2292:
2284:
2280:
2276:
2272:
2268:
2264:
2260:
2256:
2249:
2242:
2239:
2233:
2229:
2222:
2215:
2212:
2206:
2202:
2195:
2188:
2185:
2180:
2176:
2171:
2166:
2162:
2158:
2151:
2148:
2144:
2139:
2136:
2131:
2127:
2123:
2119:
2115:
2111:
2106:
2101:
2097:
2093:
2092:
2087:
2086:Seymour, Paul
2083:
2079:
2075:
2069:
2066:
2061:
2057:
2052:
2047:
2043:
2039:
2038:
2033:
2029:
2028:Seymour, Paul
2025:
2021:
2015:
2012:
2007:
2003:
1999:
1995:
1991:
1987:
1983:
1977:
1974:
1970:
1965:
1962:
1958:
1953:
1950:
1946:
1941:
1938:
1935:
1930:
1927:
1923:
1918:
1915:
1911:
1906:
1903:
1899:
1894:
1891:
1887:
1883:
1879:
1874:
1871:
1867:
1863:
1858:
1855:
1851:
1847:
1842:
1839:
1835:
1831:
1830:Lovász (2006)
1826:
1823:
1819:
1814:
1811:
1807:
1803:
1802:Thomas (1999)
1798:
1795:
1791:
1786:
1783:
1779:
1774:
1771:
1768:
1763:
1760:
1756:
1752:
1748:
1743:
1740:
1736:
1732:
1728:
1724:
1719:
1716:
1712:
1707:
1704:
1700:
1697:, pp. 80–82;
1696:
1695:Lovász (2006)
1691:
1688:
1685:, p. 76.
1684:
1683:Lovász (2006)
1679:
1676:
1672:
1668:
1663:
1660:
1652:
1646:
1645:Lovász (2006)
1641:
1638:
1634:
1629:
1627:
1623:
1619:
1614:
1612:
1608:
1604:
1600:
1599:Lovász (2006)
1595:
1593:
1589:
1585:
1581:
1580:Lovász (2006)
1576:
1574:
1570:
1564:
1562:
1560:
1556:
1552:
1548:
1544:
1540:
1536:
1531:
1529:
1525:
1521:
1517:
1513:
1509:
1505:
1501:
1497:
1493:
1489:
1485:
1481:
1477:
1473:
1469:
1465:
1461:
1457:
1453:
1449:
1445:
1441:
1437:
1433:
1425:
1423:
1418:
1415:
1414:utility graph
1411:
1407:
1403:
1399:
1395:
1391:
1387:
1383:
1379:
1375:
1370:
1368:
1364:
1360:
1356:
1351:
1347:
1343:
1339:
1335:
1331:
1327:
1323:
1319:
1315:
1311:
1307:
1303:
1299:
1291:
1289:
1287:
1283:
1279:
1275:
1271:
1270:shallow minor
1263:
1261:
1259:
1255:
1251:
1250:graph drawing
1246:
1242:
1240:
1236:
1232:
1228:
1224:
1220:
1216:
1212:
1208:
1204:
1200:
1195:
1193:
1189:
1185:
1181:
1177:
1173:
1169:
1165:
1161:
1157:
1153:
1149:
1145:
1141:
1137:
1133:
1125:
1123:
1121:
1117:
1113:
1109:
1105:
1104:induced minor
1102:is called an
1101:
1093:
1091:
1089:
1085:
1079:
1077:
1070:
1067:
1063:
1059:
1055:
1051:
1047:
1043:
1039:
1035:
1027:
1022:
1020:
1015:
1008:
1004:
997:
990:
983:
979:
975:
971:
967:
963:
959:
955:
951:
947:
943:
939:
935:
931:
927:
923:
918:
908:
904:
900:
896:
892:
888:
884:
880:
876:
872:
868:
863:
861:
857:
853:
849:
845:
841:
837:
831:
823:
821:
819:
815:
814:edge coloring
811:
808:
804:
800:
799:snark theorem
796:
790:
785:
779:
772:
767:
755:
747:
742:
722:
714:
706:
687:
657:
649:
624:
598:
595:
592:
587:
581:
573:
551:
548:
545:
540:
534:
526:
485:
482:
479:
474:
471:
465:
440:
433:, the simple
427:
425:
421:
417:
413:
401:
396:
394:
390:
371:
367:
357:
350:
344:
340:
336:
332:
328:
317:itself), and
308:
304:
303:partial order
300:
292:
290:
288:
283:
281:
276:
274:
268:
266:
260:
258:
254:
246:
244:
240:
236:
232:
228:
210:
208:
207:pseudoforests
203:
201:
197:
193:
189:
185:
181:
176:
158:
147:
139:
137:
135:
131:
130:color a graph
127:
119:
114:
112:
96:
92:
84:
80:
72:
68:
64:
60:
55:
53:
49:
34:of the graph
33:
26:
22:
3360:
3335:
3331:
3303:
3299:
3277:
3271:
3238:
3232:
3211:
3182:
3176:
3164:
3132:
3126:
3105:(1): 43–76,
3102:
3096:
3070:
3064:
3043:
3018:
3012:
2989:(1): 39–61,
2986:
2980:
2948:
2944:
2926:
2900:
2896:
2886:Pegg, Ed Jr.
2851:
2819:
2815:
2799:(1): 75–86,
2796:
2790:
2762:
2758:
2748:
2744:
2726:
2720:
2694:
2688:
2678:
2674:
2646:math/0001128
2636:
2630:
2600:
2594:
2544:
2541:Algorithmica
2540:
2513:(1): 11–23,
2510:
2509:, Series B,
2504:
2485:Graph Theory
2484:
2467:
2439:
2436:Algorithmica
2435:
2418:
2393:
2387:
2380:Bollobás, B.
2353:
2318:
2312:
2261:(1): 69–84.
2258:
2255:Algorithmica
2254:
2241:
2231:
2227:
2214:
2204:
2200:
2187:
2160:
2156:
2150:
2138:
2095:
2094:, Series B,
2089:
2068:
2044:(1): 20–29,
2041:
2040:, Series B,
2035:
2014:
1989:
1976:
1964:
1952:
1940:
1929:
1917:
1912:, p. 22
1910:Diestel 2005
1905:
1900:, p. 20
1898:Diestel 2005
1893:
1873:
1857:
1841:
1825:
1813:
1797:
1785:
1773:
1767:Grohe (2003)
1762:
1742:
1718:
1711:Mader (1967)
1706:
1690:
1678:
1662:
1650:
1640:
1558:
1554:
1550:
1546:
1542:
1539:planar graph
1534:
1532:
1515:
1511:
1507:
1499:
1495:
1491:
1487:
1483:
1479:
1475:
1471:
1463:
1459:
1455:
1451:
1443:
1439:
1435:
1429:
1416:
1410:planar graph
1405:
1393:
1389:
1385:
1381:
1371:
1362:
1358:
1349:
1345:
1341:
1337:
1333:
1329:
1325:
1317:
1313:
1309:
1305:
1301:
1297:
1295:
1277:
1273:
1267:
1247:
1243:
1238:
1234:
1230:
1226:
1222:
1218:
1214:
1210:
1206:
1202:
1198:
1196:
1191:
1187:
1183:
1179:
1175:
1171:
1168:(v,u), (u,w)
1167:
1163:
1159:
1155:
1151:
1147:
1143:
1139:
1135:
1131:
1129:
1119:
1115:
1111:
1107:
1103:
1099:
1097:
1087:
1083:
1080:
1068:
1061:
1049:
1041:
1037:
1036:is called a
1033:
1031:
1013:
1006:
1005:, while the
1003:Wagner graph
995:
988:
981:
977:
969:
957:
954:planar graph
948:has bounded
945:
936:has bounded
933:
924:has bounded
921:
919:
902:
898:
894:
890:
886:
882:
874:
870:
866:
864:
848:planar graph
844:minor-closed
843:
839:
835:
833:
820:as a minor.
788:
777:
770:
743:
685:
428:
397:
393:Klaus Wagner
369:
365:
355:
348:
335:Paul Seymour
296:
284:
279:
277:
269:
261:
256:
252:
250:
238:
234:
230:
226:
211:
204:
177:
143:
115:
82:
70:
56:
31:
30:is called a
21:graph theory
18:
3306:: 570–590,
2937:Reed, Bruce
2717:Reed, Bruce
2384:Erdős, Paul
2098:: 219–228,
2024:Reed, Bruce
2020:Geelen, Jim
1986:Reed, Bruce
1922:Ding (1996)
1886:Hall (1943)
1806:Pegg (2002)
1561:is planar.
1537:is a fixed
1466:contains a
1448:cycle graph
1272:of a graph
1106:of a graph
1046:subdivision
1040:of a graph
942:path graphs
917:as minors.
838:is also in
803:W. T. Tutte
426:of graphs.
327:deep result
212:A function
192:multigraphs
140:Definitions
3375:Categories
3300:Math. Ann.
2363:1510.07135
2301:Alon, Noga
2293:References
2078:Kalai, Gil
1426:Algorithms
1136:immersions
1054:isomorphic
1023:Variations
966:apex graph
938:tree-depth
807:bridgeless
629:, and any
572:degeneracy
412:clique-sum
373:such that
307:transitive
224:, one has
184:self-loops
3362:MathWorld
3338:: 280–285
3320:123534907
3263:124801301
2836:120261785
2681:: 133–143
2275:0178-4617
2165:CiteSeerX
2105:1312.0210
1494:), where
1438:contains
1388:whenever
1322:odd minor
950:treewidth
926:pathwidth
852:embedding
850:, or any
705:treewidth
596:
549:
483:
3161:(1993),
2888:(2002),
2850:(2012),
2779:15736799
2663:11751235
2619:16587284
2130:14571660
2006:17385711
1545:whether
1502:and the
1432:deciding
1365:-vertex
1282:diameter
1154:, where
1098:A graph
1058:subgraph
1032:A graph
962:diameter
633:-vertex
416:embedded
343:infinite
341:: if an
301:forms a
299:relation
196:cut-edge
77:nor the
48:vertices
3243:Bibcode
3224:1725004
3199:9608738
2905:Bibcode
2878:2920058
2751:: 37–58
2579:3172160
2571:1759751
2529:1368512
2417:(ed.),
2368:Bibcode
2345:1065053
2337:1990903
2283:6204674
2234:: 1–21.
2207:: 1–21.
2122:3425242
2060:2467815
1454:, then
1357:, that
1140:lifting
1138:. The
1132:lifting
1074:in the
689:⁄
247:Example
50:and by
3318:
3261:
3222:
3197:
2965:760001
2963:
2876:
2866:
2834:
2777:
2661:
2617:
2577:
2569:
2527:
2492:
2456:390856
2454:
2343:
2335:
2281:
2273:
2167:
2128:
2120:
2058:
2004:
1150:, and
956:, and
930:forest
764:has a
525:degree
439:sparse
89:. The
63:planar
3316:S2CID
3259:S2CID
3216:(PDF)
3195:S2CID
3173:(PDF)
2961:S2CID
2893:(PDF)
2832:S2CID
2775:S2CID
2659:S2CID
2641:arXiv
2615:S2CID
2575:S2CID
2549:arXiv
2452:S2CID
2358:arXiv
2333:JSTOR
2279:S2CID
2251:(PDF)
2224:(PDF)
2197:(PDF)
2126:S2CID
2100:arXiv
2002:S2CID
1565:Notes
1446:is a
1408:is a
1320:. An
1184:(v,w)
1180:(v,w)
1176:(u,w)
1172:(v,u)
1160:(u,w)
1156:(v,u)
1056:to a
1044:if a
913:nor K
860:genus
768:with
420:genus
368:<
345:list
155:if a
32:minor
23:, an
2864:ISBN
2490:ISBN
2271:ISSN
1190:and
1174:and
1158:and
987:and
881:for
744:The
515:has
445:has
361:, …)
333:and
321:and
233:) ≤
200:rank
186:and
3308:doi
3304:114
3282:doi
3251:doi
3187:doi
3137:doi
3107:doi
3075:doi
3023:doi
2991:doi
2953:doi
2913:doi
2856:doi
2824:doi
2820:174
2801:doi
2767:doi
2731:doi
2727:102
2699:doi
2651:doi
2605:doi
2559:doi
2515:doi
2472:doi
2444:doi
2398:doi
2323:doi
2263:doi
2175:doi
2110:doi
2096:116
2046:doi
1994:doi
1420:3,3
1256:of
1248:In
1164:vuw
1060:of
1052:is
1048:of
1010:3,3
992:3,3
915:3,3
865:If
791:≤ 6
780:= 5
773:– 1
756:on
593:log
546:log
480:log
329:by
270:G.
262:H.
159:to
109:in
86:3,3
38:if
19:In
3377::
3359:.
3334:,
3314:,
3302:,
3278:81
3276:,
3257:,
3249:,
3239:95
3237:,
3220:MR
3193:,
3183:13
3181:,
3175:,
3157:;
3153:;
3133:92
3131:,
3121:;
3103:89
3101:,
3091:;
3071:63
3069:,
3059:;
3038:;
3019:41
3017:,
3007:;
2987:35
2985:,
2975:;
2959:,
2947:,
2939:;
2911:,
2901:49
2899:,
2895:,
2874:MR
2872:,
2862:,
2846:;
2830:,
2818:,
2797:43
2795:,
2773:,
2761:,
2749:38
2725:,
2695:49
2693:,
2679:88
2677:,
2657:,
2649:,
2637:23
2635:,
2613:,
2601:35
2599:,
2589:;
2573:,
2567:MR
2565:,
2557:,
2545:27
2543:,
2525:MR
2523:,
2511:66
2450:,
2440:40
2438:,
2434:,
2392:,
2366:,
2356:,
2341:MR
2339:,
2331:,
2317:,
2307:;
2303:;
2277:.
2269:.
2259:64
2257:.
2253:.
2232:11
2230:.
2226:.
2205:11
2203:.
2199:.
2173:.
2159:.
2124:,
2118:MR
2116:,
2108:,
2084:;
2076:;
2056:MR
2054:,
2042:99
2034:,
2026:;
2000:,
1984:;
1884:;
1880:;
1864:;
1848:;
1804:;
1753:;
1749:;
1733:;
1729:;
1725:;
1625:^
1610:^
1591:^
1572:^
1268:A
1146:,
1019:.
944:,
932:,
741:.
699:,
354:,
259::
243:.
175:.
54:.
3365:.
3340:.
3336:2
3323:.
3310::
3291:.
3284::
3266:.
3253::
3245::
3227:.
3202:.
3189::
3168:6
3165:K
3146:.
3139::
3114:.
3109::
3084:.
3077::
3052:.
3025::
3000:.
2993::
2968:.
2955::
2949:5
2932:.
2920:.
2915::
2907::
2881:.
2858::
2839:.
2826::
2810:.
2803::
2782:.
2769::
2763:4
2753:.
2733::
2708:.
2701::
2683:.
2666:.
2653::
2643::
2622:.
2607::
2582:.
2561::
2551::
2532:.
2517::
2499:.
2474::
2459:.
2446::
2423:.
2405:.
2400::
2394:1
2375:.
2370::
2360::
2348:.
2325::
2319:3
2285:.
2265::
2181:.
2177::
2161:8
2145:.
2133:.
2112::
2102::
2063:.
2048::
2009:.
1996::
1959:.
1947:.
1924:.
1888:.
1868:.
1852:.
1836:.
1820:.
1808:.
1792:.
1780:.
1757:.
1737:.
1713:.
1701:.
1673:.
1654:3
1651:K
1635:.
1620:.
1605:.
1586:.
1559:G
1555:H
1551:G
1547:H
1543:G
1535:H
1516:n
1514:(
1512:O
1508:H
1500:G
1496:n
1492:n
1490:(
1488:O
1484:G
1480:H
1476:H
1472:G
1464:G
1460:G
1456:H
1452:G
1444:H
1440:H
1436:G
1417:K
1406:G
1394:G
1390:H
1386:G
1382:H
1363:k
1359:k
1350:G
1346:G
1342:G
1338:G
1334:H
1330:G
1326:H
1318:G
1314:H
1310:G
1306:H
1302:G
1298:H
1278:G
1274:G
1239:G
1235:H
1231:G
1227:H
1223:G
1219:H
1215:G
1211:H
1207:G
1203:G
1199:H
1192:w
1188:v
1152:w
1148:u
1144:v
1120:H
1116:G
1112:G
1108:G
1100:H
1088:k
1084:k
1072:5
1069:K
1062:G
1050:H
1042:G
1034:H
1017:5
1014:K
1007:K
999:5
996:K
989:K
985:5
982:K
978:H
970:H
958:F
946:F
934:F
922:F
911:5
903:X
899:X
895:F
891:X
887:F
883:F
875:X
871:F
867:F
840:F
836:F
789:k
778:k
771:k
762:G
758:k
750:G
728:)
723:n
718:(
715:O
701:H
697:H
691:3
686:n
684:2
678:G
663:)
658:n
653:(
650:O
639:G
635:H
631:n
627:H
619:H
604:)
599:h
588:h
585:(
582:O
557:)
552:h
541:h
538:(
535:O
521:H
517:h
513:H
508:h
506:K
491:)
486:h
475:h
472:n
469:(
466:O
455:H
451:n
447:h
443:H
435:H
431:H
408:H
404:H
384:j
382:G
377:i
375:G
370:j
366:i
359:2
356:G
352:1
349:G
347:(
323:H
319:G
315:G
311:G
280:G
257:G
253:H
241:)
239:G
237:(
235:f
231:H
229:(
227:f
222:G
218:H
214:f
173:H
169:G
165:G
161:H
153:G
149:H
122:H
107:G
103:H
99:H
83:K
74:5
71:K
44:G
40:H
36:G
28:H
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.