图子式
图子式的提出源自瓦格纳定理,这个定理表明:当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时,这个图才是平面图。[1] 罗伯逊-西摩定理表明,对于任何在图上删除点或边或收缩边保留的性质,类似的禁子式表征(forbidden minor characterization)也存在。[2] 给定图G和图H,可以在多项式时间内判断H是否是G的子式。[3] 连同上述禁子式表征,这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。[4] 其他涉及到图子式的定理和猜想包括图结构定理、Hadwiger猜想等。
定义
边收缩(contraction)是在图上移除一条边同时合并这条边的两个邻点。一个无向图H是另一个无向图G的子式,如果G通过一系列的收缩边、删除边、删除孤立点可以得到一个同构于H的图。这一系列收缩和删除操作的顺序不影响最后得到的图H。
例子
H是G的子式:
H.
G.
以下显示了如何构造子式。首先去除图G中虚线边,再去掉孤立的顶点,最后对灰色边进行边收缩即得到图H。
主要结论和猜想
可以很直接地验证,在同构意义上,图子式关系是一个偏序关系:它满足自反性(自己是自己的子式)、反对称性(图G和H互为子式仅当它们同构)、传递性(图G的子式的子式也是图G的子式)。尼尔·罗伯逊和保罗·西摩提出了一个更深刻的结论:图子式关系实际上是一种预良序关系:给定一串无穷的图序列G1, G2,...总是存在i < j,使得 Gi是Gj的子式。一个等价的表述是,任意的一簇图的集合必然只有有限个子式意义下的极小元[5]。这个结论验证了先前的一个猜想:瓦格纳猜想。它很早就被克拉斯·瓦格纳提出,直至1970年才发表。[6]
在他们证明的过程中,西摩和罗伯逊也同时证明了图结构定理。对于一个给定的图H,这个定理刻画了不包含H-子式的图的结构。这个定理的严格表述又长又复杂,但是简而言之,它证明了这样一个图必须具有由嵌在有界亏格曲面上的图以小方式修改而成的图的团和结构。因此,他们的理论建立了图子式和图的拓扑嵌入之间的基本联系。[7]
对于任意图H,无H-子式的简单图必须是稀疏的,即图的边数小于等于一个常数倍的图的阶数[8]。更精确地,如果图H有h个点,那么有n个顶点的不包含H-子式的简单图G有至多条边。不包含Kh-子式的图至少有这么多条边。[9]因此,G的平均度是级别的。更进一步,不包含H-子式的图有一个和平面图分割定理类似的分割定理:给定H和任意不包含H-子式的n阶图G,可以找到个G的顶点,使得删除这些点可以将G分成两个(可能不连通的)子图,使得每个子图有至多2n/3个顶点。[10]更强的结论是,对于任意的图H,不包含H-子式的n阶图G的树宽是数量级的。[11]
Hadwiger猜想表明,如果图G不包含k阶完全图子式,那么G可以被(k − 1)-着色[12]。k = 5的情况即为四色定理。Hadwiger猜想在k ≤ 6的情况下已经被证实[13],但是更一般的情况下还没有定论。Bollobás,Catlin & Erdős (1980) 称它为“图论中最深刻的尚未解决的问题之一”。另一个将四色定理和图子式联系起来的猜想是snark猜想,它表明任意无割边的3-正则图,如果它的边色数等于4,那么佩特森图一定是它的子式。[14]
注释
- Lovász (2006), p. 77; Wagner (1937a).
- Lovász (2006), theorem 4, p. 78; Robertson & Seymour (2004).
- Robertson & Seymour (1995).
- Fellows & Langston (1988).
- Diestel (2005), Chapter 12: Minors, Trees, and WQO; Robertson & Seymour (2004).
- Lovász (2006), p. 76.
- Lovász (2006), pp. 80–82; Robertson & Seymour (2003).
- Mader (1967).
- Kostochka (1982); Kostochka (1984); Thomason (1984); Thomason (2001).
- Alon,Seymour & Thomas (1990); Plotkin,Rao & Smith (1994); Reed & Wood (2009).
- Grohe (2003)
- Hadwiger (1943)
- Robertson,Seymour & Thomas (1993).
- Thomas (1999); Pegg (2002).
参考文献
- Alon, Noga; Seymour, Paul; Thomas, Robin, , 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, , 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, , Tamassia, Roberto (编), , 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., , , Lecture Notes in Computer Science 2462, Springer-Verlag: 67–80, 2002, doi:10.1007/3-540-45753-4_8 (英语)
- Diestel, Reinhard, 3rd, Berlin, New York: Springer-Verlag, 2005 [2019-04-25], ISBN 978-3-540-26183-4, (原始内容存档于2011-07-28) (英语).
- Ding, Guoli, , Journal of Combinatorial Theory, Series B, 1996, 66 (1): 11–23, MR 1368512, doi:10.1006/jctb.1996.0002 (英语).
- Eppstein, David, , Algorithmica, 2000, 27: 275–291, MR 1759751, arXiv:math.CO/9907126, doi:10.1007/s004530010020 (英语).
- Fellows, Michael R.; Langston, Michael A., , Journal of the ACM, 1988, 35 (3): 727–739, doi:10.1145/44483.44491 (英语).
- Grohe, Martin, , Combinatorica, 2003, 23 (4): 613–632, arXiv:math/0001128, doi:10.1007/s00493-003-0037-9 (英语).
- Hadwiger, Hugo, , Vierteljschr. Naturforsch. Ges. Zürich, 1943, 88: 133–143 (英语).
- Hall, Dick Wick, , 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, , Journal of Combinatorial Theory, Series B, March 2012, 102 (2): 424–435, doi:10.1016/j.jctb.2011.07.004 (英语)
- Kostochka, Alexandr V., , Metody Diskret. Analiz., 1982, 38: 37–58 (俄语).
- Kostochka, Alexandr V., , Combinatorica, 1984, 4: 307–316, doi:10.1007/BF02579141 (英语).
- Lovász, László, , Bulletin of the American Mathematical Society, 2006, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8 (英语).
- Mader, Wolfgang, , Mathematische Annalen, 1967, 174 (4): 265–268, doi:10.1007/BF01364272 (英语).
- Nešetřil, Jaroslav; Ossona de Mendez, Patrice, , 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., (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., , : 462–470, 1994 (英语).
- Reed, Bruce; Wood, David R., , ACM Transactions on Algorithms, 2009, 5 (4): Article 39, doi:10.1145/1597036.1597043 (英语).
- Robertson, Neil; Seymour, Paul, , Journal of Combinatorial Theory, Series B, 1983, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5 (英语).
- Robertson, Neil; Seymour, Paul D., , Journal of Combinatorial Theory, Series B, 1986, 41 (1): 92–114, doi:10.1016/0095-8956(86)90030-4 (英语)
- Robertson, Neil; Seymour, Paul D., , Robertson, Neil; Seymour, Paul (编), , Contemporary Mathematics 147, American Mathematical Society: 669–675, 1993 (英语).
- Robertson, Neil; Seymour, Paul D., , Journal of Combinatorial Theory, Series B, 1995, 63 (1): 65–110, doi:10.1006/jctb.1995.1006 (英语).
- Robertson, Neil; Seymour, Paul D., , Journal of Combinatorial Theory, Series B, 2003, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X (英语).
- Robertson, Neil; Seymour, Paul D., , 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, , (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, , Mathematical Proceedings of the Cambridge Philosophical Society, 1984, 95 (2): 261–265, Bibcode:1983MPCPS..95..261T, doi:10.1017/S0305004100061521 (英语).
- Thomason, Andrew, , Journal of Combinatorial Theory, Series B, 2001, 81 (2): 318–338, doi:10.1006/jctb.2000.2013 (英语).
- Wagner, Klaus, , Math. Ann., 1937a, 114: 570–590, doi:10.1007/BF01594196 (英语).
- Wagner, Klaus, , Deutsche Mathematik, 1937b, 2: 280–285 (英语).