瓦格纳定理
在图论中,瓦格纳理论(英:Wagner's theorem)是平面图的禁图表征,以Klaus Wagner的命名。 该定理说:当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候,那么该图就是平面的。
这是图子式论最早的结果之一,也是罗伯逊–西摩定理(Robertson-Seymour theorem)的先驱。
库拉托夫斯基定理的关系
瓦格纳1937年发表了证明。[1] 库拉托夫斯基以前1930年出版了自己库拉托夫斯基理论。[2]
根据该定理,当且仅当图的子图的细分不包含那些禁图K5 和 K3,3。
瓦格纳定理意味着库拉托夫斯基,所以是更普遍的。[3]
参考资料
- ^ Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 1937, 114: 570–590, doi:10.1007/BF01594196
- ^ Kuratowski, Kazimierz, Sur le problème des courbes gauches en topologie (PDF), Fund. Math., 1930, 15: 271–283 [2019-04-25], (原始内容 (PDF)存档于2018-07-23) (法语).
- ^ Bondy, J. A.; Murty, U.S.R., Graph Theory, Graduate Texts in Mathematics 244, Springer: 269, 2008, ISBN 9781846289699.