fbpx
维基百科

图子式

四月 09, 2024

在图论中，如果无向图H可以通过图G删除边和顶点或收缩边得到，则称H为G的子式（minor）或次图。

图子式的提出源自瓦格纳定理，这个定理表明：当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时，这个图才是平面图。[1]罗伯逊-西摩定理（英语：Robertson–Seymour theorem）表明，对于任何在图上删除点或边或收缩边保留的性质，类似的禁子式表征（英语：forbidden minor characterization）（forbidden minor characterization）也存在。[2] 给定图G和图H，可以在多项式时间内判断H是否是G的子式。[3] 连同上述禁子式表征，这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。[4] 其他涉及到图子式的定理和猜想包括图结构定理（英语：graph structure theorem）、Hadwiger猜想（英语：Hadwiger conjecture (graph_theory)）等。

定义 编辑

边收缩（contraction）是在图上移除一条边同时合并这条边的两个邻点。一个无向图H是另一个无向图G的子式，如果G通过一系列的收缩边、删除边、删除孤立点可以得到一个同构于H的图。这一系列收缩和删除操作的顺序不影响最后得到的图H。

例子 编辑

H是G的子式：

H.  

G.  

以下显示了如何构造子式。首先去除图G中虚线边，再去掉孤立的顶点，最后对灰色边进行边收缩即得到图H。

 

主要结论和猜想 编辑

可以很直接地验证，在同构意义上，图子式关系是一个偏序关系：它满足自反性（自己是自己的子式）、反对称性（图G和H互为子式仅当它们同构）、传递性（图G的子式的子式也是图G的子式）。尼尔·罗伯逊（英语：Neil Robertson (mathematician)）和保罗·西摩（英语：Paul Seymour (mathematician)）提出了一个更深刻的结论：图子式关系实际上是一种良擬序关系：给定一串无穷的图序列G1, G2,...总是存在i < j，使得 Gi是Gj的子式。一个等价的表述是，任意的一簇图的集合必然只有有限个子式意义下的极小元[5]。这个结论验证了先前的一个猜想：瓦格纳猜想。它很早就被克拉斯·瓦格纳（英语：Klaus Wagner）提出，直至1970年才发表。[6]

在他们证明的过程中，西摩和罗伯逊也同时证明了图结构定理（英语：graph structure theorem）。对于一个给定的图H，这个定理刻画了不包含H-子式的图的结构。这个定理的严格表述又长又复杂，但是简而言之，它证明了这样一个图必须具有由嵌在有界亏格曲面上的图以小方式修改而成的图的团和（英语：Clique-sum）结构。因此，他们的理论建立了图子式和图的拓扑嵌入之间的基本联系。[7]

对于任意图H，无H-子式的简单图必须是稀疏的，即图的边数小于等于一个常数倍的图的阶数[8]。更精确地，如果图H有h个点，那么有n个顶点的不包含H-子式的简单图G有至多 条边。不包含Kh-子式的图至少有这么多条边。[9]因此，G的平均度是 级别的。更进一步，不包含H-子式的图有一个和平面图分割定理（英语：planar separator theorem）类似的分割定理：给定H和任意不包含H-子式的n阶图G，可以找到 个G的顶点，使得删除这些点可以将G分成两个（可能不连通的）子图，使得每个子图有至多2n/3个顶点。[10]更强的结论是，对于任意的图H，不包含H-子式的n阶图G的树宽是 数量级的。[11]

Hadwiger猜想（英语：Hadwiger conjecture (graph_theory)）表明，如果图G不包含k阶完全图子式，那么G可以被(k − 1)-着色[12]。k = 5的情况即为四色定理。Hadwiger猜想在k ≤ 6的情况下已经被证实[13]，但是更一般的情况下还没有定论。Bollobás，Catlin & Erdős (1980) 称它为“图论中最深刻的尚未解决的问题之一”。另一个将四色定理和图子式联系起来的猜想是snark猜想（英语：Snark (graph theory)），它表明任意无割边的3-正则图，如果它的边色数等于4，那么佩特森图一定是它的子式。[14]

参见 编辑

注释 编辑

  1. ^ Lovász (2006), p. 77; Wagner (1937a).
  2. ^ Lovász (2006), theorem 4, p. 78; Robertson & Seymour (2004).
  3. ^ Robertson & Seymour (1995).
  4. ^ Fellows & Langston (1988).
  5. ^ Diestel (2005), Chapter 12: Minors, Trees, and WQO; Robertson & Seymour (2004).
  6. ^ Lovász (2006), p. 76.
  7. ^ Lovász (2006), pp. 80–82; Robertson & Seymour (2003).
  8. ^ Mader (1967).
  9. ^ Kostochka (1982); Kostochka (1984); Thomason (1984); Thomason (2001).
  10. ^ Alon，Seymour & Thomas (1990); Plotkin，Rao & Smith (1994); Reed & Wood (2009).
  11. ^ Grohe (2003)
  12. ^ Hadwiger (1943)
  13. ^ Robertson，Seymour & Thomas (1993).
  14. ^ Thomas (1999); Pegg (2002).

参考文献 编辑

  • Alon, Noga; Seymour, Paul; Thomas, Robin, A separator theorem for nonplanar graphs, Journal of the American Mathematical Society, 1990, 3 (4): 801–808 [2019-04-25], JSTOR 1990903, MR 1065053, doi:10.2307/1990903, （原始内容于2019-02-14） （英语） .
  • Błasiok, Jarosław; Kamiński, Marcin; Raymond, Jean-Florent; Trunck, Théophile, Induced minors and well-quasi-ordering, Bibcode:2015arXiv151007135B, arXiv:1510.07135   （英语） .
  • Bollobás, B.; Catlin, P. A.; Erdős, Paul, (PDF), European Journal of Combinatorics, 1980, 1: 195–199 [2019-04-25], doi:10.1016/s0195-6698(80)80001-1, （原始内容 (PDF)存档于2009-03-18） （英语） .
  • Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael; Mutzel, Petra, Crossings and planarization, Tamassia, Roberto (编), Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2014 （英语） .
  • Demaine, Erik D.; Hajiaghayi, MohammadTaghi, , Algorithmica, 2004, 40 (3): 211–215 [2019-04-25], doi:10.1007/s00453-004-1106-1, （原始内容存档于2019-09-20） （英语） .
  • Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M., 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor, Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), Lecture Notes in Computer Science 2462, Springer-Verlag: 67–80, 2002, doi:10.1007/3-540-45753-4_8 （英语） 
  • Diestel, Reinhard, Graph Theory 3rd, Berlin, New York: Springer-Verlag, 2005 [2019-04-25], ISBN 978-3-540-26183-4, （原始内容于2011-07-28） （英语） .
  • Ding, Guoli, Excluding a long double path minor, Journal of Combinatorial Theory, Series B, 1996, 66 (1): 11–23, MR 1368512, doi:10.1006/jctb.1996.0002 （英语） .
  • Eppstein, David, Diameter and treewidth in minor-closed graph families, Algorithmica, 2000, 27: 275–291, MR 1759751, arXiv:math.CO/9907126  , doi:10.1007/s004530010020 （英语） .
  • Fellows, Michael R.; Langston, Michael A., Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM, 1988, 35 (3): 727–739, doi:10.1145/44483.44491 （英语） .
  • Grohe, Martin, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 2003, 23 (4): 613–632, arXiv:math/0001128  , doi:10.1007/s00493-003-0037-9 （英语） .
  • Hadwiger, Hugo, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich, 1943, 88: 133–143 （英语） .
  • Hall, Dick Wick, A note on primitive skew curves, Bulletin of the American Mathematical Society, 1943, 49 (12): 935–936, doi:10.1090/S0002-9904-1943-08065-2 （英语） .
  • Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce, The disjoint paths problem in quadratic time, Journal of Combinatorial Theory, Series B, March 2012, 102 (2): 424–435, doi:10.1016/j.jctb.2011.07.004 （英语） 
  • Kostochka, Alexandr V., The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret. Analiz., 1982, 38: 37–58 （俄语） .
  • Kostochka, Alexandr V., Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica, 1984, 4: 307–316, doi:10.1007/BF02579141 （英语） .
  • Lovász, László, Graph minor theory, Bulletin of the American Mathematical Society, 2006, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8 （英语） .
  • Mader, Wolfgang, Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Mathematische Annalen, 1967, 174 (4): 265–268, doi:10.1007/BF01364272 （英语） .
  • Nešetřil, Jaroslav; Ossona de Mendez, Patrice, Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer: 62–65, 2012, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4 （英语） .
  • Pegg, Ed, Jr., Book Review: The Colossal Book of Mathematics (PDF), Notices of the American Mathematical Society, 2002, 49 (9): 1084–1086 [2019-04-25], Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756, （原始内容 (PDF)于2019-04-02） （英语） .
  • Plotkin, Serge; Rao, Satish; Smith, Warren D., Shallow excluded minors and improved graph decompositions, Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994): 462–470, 1994 （英语） .
  • Reed, Bruce; Wood, David R., A linear-time algorithm to find a separator in a graph excluding a minor, ACM Transactions on Algorithms, 2009, 5 (4): Article 39, doi:10.1145/1597036.1597043 （英语） .
  • Robertson, Neil; Seymour, Paul, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, 1983, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5 （英语） .
  • Robertson, Neil; Seymour, Paul D., Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory, Series B, 1986, 41 (1): 92–114, doi:10.1016/0095-8956(86)90030-4 （英语） 
  • Robertson, Neil; Seymour, Paul D., Excluding a graph with one crossing, Robertson, Neil; Seymour, Paul (编), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics 147, American Mathematical Society: 669–675, 1993 （英语） .
  • Robertson, Neil; Seymour, Paul D., Graph Minors. XIII. The disjoint paths problem, Journal of Combinatorial Theory, Series B, 1995, 63 (1): 65–110, doi:10.1006/jctb.1995.1006 （英语） .
  • Robertson, Neil; Seymour, Paul D., Graph Minors. XVI. Excluding a non-planar graph, Journal of Combinatorial Theory, Series B, 2003, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X （英语） .
  • Robertson, Neil; Seymour, Paul D., Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory, Series B, 2004, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001 （英语） .
  • Robertson, Neil; Seymour, Paul; Thomas, Robin, (PDF), Combinatorica, 1993, 13: 279–361 [2019-04-25], doi:10.1007/BF01202354, （原始内容 (PDF)存档于2009-04-10） （英语） .
  • Thomas, Robin, Recent excluded minor theorems for graphs, (PDF), London Math. Soc. Lecture Note Ser. 267, Cambridge: Cambridge Univ. Press: 201–222, 1999 [2019-04-25], MR 1725004, （原始内容 (PDF)存档于2016-08-03） （英语） .
  • Thomason, Andrew, An extremal function for contractions of graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 1984, 95 (2): 261–265, Bibcode:1983MPCPS..95..261T, doi:10.1017/S0305004100061521 （英语） .
  • Thomason, Andrew, The extremal function for complete minors, Journal of Combinatorial Theory, Series B, 2001, 81 (2): 318–338, doi:10.1006/jctb.2000.2013 （英语） .
  • Wagner, Klaus, Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 1937a, 114: 570–590, doi:10.1007/BF01594196 （英语） .
  • Wagner, Klaus, Über eine Erweiterung des Satzes von Kuratowski, Deutsche Mathematik, 1937b, 2: 280–285 （英语） .

外部链接 编辑

四月 09, 2024
图子式, 此條目目前正依照en, graph, minor上的内容进行翻译, 2020年12月22日, 如果您擅长翻译, 並清楚本條目的領域, 欢迎协助翻譯, 改善或校对本條目, 此外, 长期闲置, 未翻譯或影響閱讀的内容可能会被移除, 目前的翻译进度为, 在图论中, 如果无向图h可以通过图g删除边和顶点或收缩边得到, 则称h为g的子式, minor, 或次图, 的提出源自瓦格纳定理, 这个定理表明, 当且仅当一个图不存在完全图k5和完全二分图k3, 3的子式时, 这个图才是平面图, 罗伯逊, 西摩定理, 英语, . 此條目目前正依照en Graph minor上的内容进行翻译 2020年12月22日 如果您擅长翻译 並清楚本條目的領域 欢迎协助翻譯 改善或校对本條目 此外 长期闲置 未翻譯或影響閱讀的内容可能会被移除 目前的翻译进度为 50 在图论中 如果无向图H可以通过图G删除边和顶点或收缩边得到 则称H为G的子式 minor 或次图 图子式的提出源自瓦格纳定理 这个定理表明 当且仅当一个图不存在完全图K5和完全二分图K3 3的子式时 这个图才是平面图 1 罗伯逊 西摩定理 英语 Robertson Seymour theorem 表明 对于任何在图上删除点或边或收缩边保留的性质 类似的禁子式表征 英语 forbidden minor characterization forbidden minor characterization 也存在 2 给定图G和图H 可以在多项式时间内判断H是否是G的子式 3 连同上述禁子式表征 这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别 4 其他涉及到图子式的定理和猜想包括图结构定理 英语 graph structure theorem Hadwiger猜想 英语 Hadwiger conjecture graph theory 等 目录 1 定义 2 例子 3 主要结论和猜想 4 参见 5 注释 6 参考文献 7 外部链接定义 编辑边收缩 contraction 是在图上移除一条边同时合并这条边的两个邻点 一个无向图H是另一个无向图G的子式 如果G通过一系列的收缩边 删除边 删除孤立点可以得到一个同构于H的图 这一系列收缩和删除操作的顺序不影响最后得到的图H 例子 编辑H是G的子式 H nbsp G nbsp 以下显示了如何构造子式 首先去除图G中虚线边 再去掉孤立的顶点 最后对灰色边进行边收缩即得到图H nbsp 主要结论和猜想 编辑可以很直接地验证 在同构意义上 图子式关系是一个偏序关系 它满足自反性 自己是自己的子式 反对称性 图G和H互为子式仅当它们同构 传递性 图G的子式的子式也是图G的子式 尼尔 罗伯逊 英语 Neil Robertson mathematician 和保罗 西摩 英语 Paul Seymour mathematician 提出了一个更深刻的结论 图子式关系实际上是一种良擬序关系 给定一串无穷的图序列G1 G2 总是存在i lt j 使得 Gi是Gj的子式 一个等价的表述是 任意的一簇图的集合必然只有有限个子式意义下的极小元 5 这个结论验证了先前的一个猜想 瓦格纳猜想 它很早就被克拉斯 瓦格纳 英语 Klaus Wagner 提出 直至1970年才发表 6 在他们证明的过程中 西摩和罗伯逊也同时证明了图结构定理 英语 graph structure theorem 对于一个给定的图H 这个定理刻画了不包含H 子式的图的结构 这个定理的严格表述又长又复杂 但是简而言之 它证明了这样一个图必须具有由嵌在有界亏格曲面上的图以小方式修改而成的图的团和 英语 Clique sum 结构 因此 他们的理论建立了图子式和图的拓扑嵌入之间的基本联系 7 对于任意图H 无H 子式的简单图必须是稀疏的 即图的边数小于等于一个常数倍的图的阶数 8 更精确地 如果图H有h个点 那么有n个顶点的不包含H 子式的简单图G有至多O nhlog h displaystyle scriptstyle O nh sqrt log h nbsp 条边 不包含Kh 子式的图至少有这么多条边 9 因此 G的平均度是O hlog h displaystyle scriptstyle O h sqrt log h nbsp 级别的 更进一步 不包含H 子式的图有一个和平面图分割定理 英语 planar separator theorem 类似的分割定理 给定H和任意不包含H 子式的n阶图G 可以找到O n displaystyle scriptstyle O sqrt n nbsp 个G的顶点 使得删除这些点可以将G分成两个 可能不连通的 子图 使得每个子图有至多2n 3个顶点 10 更强的结论是 对于任意的图H 不包含H 子式的n阶图G的树宽是O n displaystyle scriptstyle O sqrt n nbsp 数量级的 11 Hadwiger猜想 英语 Hadwiger conjecture graph theory 表明 如果图G不包含k阶完全图子式 那么G可以被 k 1 着色 12 k 5的情况即为四色定理 Hadwiger猜想在k 6的情况下已经被证实 13 但是更一般的情况下还没有定论 Bollobas Catlin amp Erdos 1980 称它为 图论中最深刻的尚未解决的问题之一 另一个将四色定理和图子式联系起来的猜想是snark猜想 英语 Snark graph theory 它表明任意无割边的3 正则图 如果它的边色数等于4 那么佩特森图一定是它的子式 14 参见 编辑瓦格纳定理 细分 边收缩 串并图 子图 图论术语注释 编辑 Lovasz 2006 p 77 Wagner 1937a Lovasz 2006 theorem 4 p 78 Robertson amp Seymour 2004 Robertson amp Seymour 1995 Fellows amp Langston 1988 Diestel 2005 Chapter 12 Minors Trees and WQO Robertson amp Seymour 2004 Lovasz 2006 p 76 Lovasz 2006 pp 80 82 Robertson amp Seymour 2003 Mader 1967 Kostochka 1982 Kostochka 1984 Thomason 1984 Thomason 2001 Alon Seymour amp Thomas 1990 Plotkin Rao amp Smith 1994 Reed amp Wood 2009 Grohe 2003 Hadwiger 1943 Robertson Seymour amp Thomas 1993 Thomas 1999 Pegg 2002 参考文献 编辑Alon Noga Seymour Paul Thomas Robin A separator theorem for nonplanar graphs Journal of the American Mathematical Society 1990 3 4 801 808 2019 04 25 JSTOR 1990903 MR 1065053 doi 10 2307 1990903 原始内容存档于2019 02 14 英语 Blasiok Jaroslaw Kaminski Marcin Raymond Jean Florent Trunck Theophile Induced minors and well quasi ordering Bibcode 2015arXiv151007135B arXiv 1510 07135 nbsp 英语 Bollobas B Catlin P A Erdos Paul Hadwiger s conjecture is true for almost every graph PDF European Journal of Combinatorics 1980 1 195 199 2019 04 25 doi 10 1016 s0195 6698 80 80001 1 原始内容 PDF 存档于2009 03 18 英语 Buchheim Christoph Chimani Markus Gutwenger Carsten Junger Michael Mutzel Petra Crossings and planarization Tamassia Roberto 编 Handbook of Graph Drawing and Visualization Discrete Mathematics and its Applications Boca Raton CRC Press Boca Raton FL 2014 英语 Demaine Erik D Hajiaghayi MohammadTaghi Diameter and treewidth in minor closed graph families revisited Algorithmica 2004 40 3 211 215 2019 04 25 doi 10 1007 s00453 004 1106 1 原始内容存档于2019 09 20 英语 Demaine Erik D Hajiaghayi MohammadTaghi Thilikos Dimitrios M 1 5 Approximation for treewidth of graphs excluding a graph with one crossing as a minor Proc 5th International Workshop on Approximation Algorithms for Combinatorial Optimization APPROX 2002 Lecture Notes in Computer Science 2462 Springer Verlag 67 80 2002 doi 10 1007 3 540 45753 4 8 英语 Diestel Reinhard Graph Theory 3rd Berlin New York Springer Verlag 2005 2019 04 25 ISBN 978 3 540 26183 4 原始内容存档于2011 07 28 英语 Ding Guoli Excluding a long double path minor Journal of Combinatorial Theory Series B 1996 66 1 11 23 MR 1368512 doi 10 1006 jctb 1996 0002 英语 Eppstein David Diameter and treewidth in minor closed graph families Algorithmica 2000 27 275 291 MR 1759751 arXiv math CO 9907126 nbsp doi 10 1007 s004530010020 英语 Fellows Michael R Langston Michael A Nonconstructive tools for proving polynomial time decidability Journal of the ACM 1988 35 3 727 739 doi 10 1145 44483 44491 英语 Grohe Martin Local tree width excluded minors and approximation algorithms Combinatorica 2003 23 4 613 632 arXiv math 0001128 nbsp doi 10 1007 s00493 003 0037 9 英语 Hadwiger Hugo Uber eine Klassifikation der Streckenkomplexe Vierteljschr Naturforsch Ges Zurich 1943 88 133 143 英语 Hall Dick Wick A note on primitive skew curves Bulletin of the American Mathematical Society 1943 49 12 935 936 doi 10 1090 S0002 9904 1943 08065 2 英语 Kawarabayashi Ken ichi Kobayashi Yusuke Reed Bruce The disjoint paths problem in quadratic time Journal of Combinatorial Theory Series B March 2012 102 2 424 435 doi 10 1016 j jctb 2011 07 004 英语 Kostochka Alexandr V The minimum Hadwiger number for graphs with a given mean degree of vertices Metody Diskret Analiz 1982 38 37 58 俄语 Kostochka Alexandr V Lower bound of the Hadwiger number of graphs by their average degree Combinatorica 1984 4 307 316 doi 10 1007 BF02579141 英语 Lovasz Laszlo Graph minor theory Bulletin of the American Mathematical Society 2006 43 1 75 86 doi 10 1090 S0273 0979 05 01088 8 英语 Mader Wolfgang Homomorphieeigenschaften und mittlere Kantendichte von Graphen Mathematische Annalen 1967 174 4 265 268 doi 10 1007 BF01364272 英语 Nesetril Jaroslav Ossona de Mendez Patrice Sparsity Graphs Structures and Algorithms Algorithms and Combinatorics 28 Springer 62 65 2012 ISBN 978 3 642 27874 7 MR 2920058 doi 10 1007 978 3 642 27875 4 英语 Pegg Ed Jr Book Review The Colossal Book of Mathematics PDF Notices of the American Mathematical Society 2002 49 9 1084 1086 2019 04 25 Bibcode 2002ITED 49 1084A doi 10 1109 TED 2002 1003756 原始内容存档 PDF 于2019 04 02 英语 Plotkin Serge Rao Satish Smith Warren D Shallow excluded minors and improved graph decompositions Proc 5th ACM SIAM Symp on Discrete Algorithms SODA 1994 462 470 1994 英语 Reed Bruce Wood David R A linear time algorithm to find a separator in a graph excluding a minor ACM Transactions on Algorithms 2009 5 4 Article 39 doi 10 1145 1597036 1597043 英语 Robertson Neil Seymour Paul Graph minors I Excluding a forest Journal of Combinatorial Theory Series B 1983 35 1 39 61 doi 10 1016 0095 8956 83 90079 5 英语 Robertson Neil Seymour Paul D Graph minors V Excluding a planar graph Journal of Combinatorial Theory Series B 1986 41 1 92 114 doi 10 1016 0095 8956 86 90030 4 英语 Robertson Neil Seymour Paul D Excluding a graph with one crossing Robertson Neil Seymour Paul 编 Graph Structure Theory Proc AMS IMS SIAM Joint Summer Research Conference on Graph Minors Contemporary Mathematics 147 American Mathematical Society 669 675 1993 英语 Robertson Neil Seymour Paul D Graph Minors XIII The disjoint paths problem Journal of Combinatorial Theory Series B 1995 63 1 65 110 doi 10 1006 jctb 1995 1006 英语 Robertson Neil Seymour Paul D Graph Minors XVI Excluding a non planar graph Journal of Combinatorial Theory Series B 2003 89 1 43 76 doi 10 1016 S0095 8956 03 00042 X 英语 Robertson Neil Seymour Paul D Graph Minors XX Wagner s conjecture Journal of Combinatorial Theory Series B 2004 92 2 325 357 doi 10 1016 j jctb 2004 08 001 英语 Robertson Neil Seymour Paul Thomas Robin Hadwiger s conjecture for K6 free graphs PDF Combinatorica 1993 13 279 361 2019 04 25 doi 10 1007 BF01202354 原始内容 PDF 存档于2009 04 10 英语 Thomas Robin Recent excluded minor theorems for graphs Surveys in combinatorics 1999 Canterbury PDF London Math Soc Lecture Note Ser 267 Cambridge Cambridge Univ Press 201 222 1999 2019 04 25 MR 1725004 原始内容 PDF 存档于2016 08 03 英语 Thomason Andrew An extremal function for contractions of graphs Mathematical Proceedings of the Cambridge Philosophical Society 1984 95 2 261 265 Bibcode 1983MPCPS 95 261T doi 10 1017 S0305004100061521 英语 Thomason Andrew The extremal function for complete minors Journal of Combinatorial Theory Series B 2001 81 2 318 338 doi 10 1006 jctb 2000 2013 英语 Wagner Klaus Uber eine Eigenschaft der ebenen Komplexe Math Ann 1937a 114 570 590 doi 10 1007 BF01594196 英语 Wagner Klaus Uber eine Erweiterung des Satzes von Kuratowski Deutsche Mathematik 1937b 2 280 285 英语 外部链接 编辑埃里克 韦斯坦因 Graph Minor MathWorld 取自 https zh wikipedia org w index php title 图子式 amp oldid 81933861, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。