瓦格纳定理

图论中,瓦格纳理论英語:)是平面图的禁图表征,以Klaus Wagner的命名。 该定理说:当且仅当有限图的子式不包含完全图K5完全二分图K3,3 时候,那么该图就是平面的。

K5 (左) 和 K3,3 (右) 是非平面彼得森图图子式 (彩色小圆圈和黑色边,删除红色顶点,收缩每个黄色圆圈内的边)。
两个平面图以及瓦格纳图的“clique-sum”,创建无K5图。

这是图子式论最早的结果之一,也是罗伯逊–西摩定理(Robertson-Seymour theorem)的先驱。

库拉托夫斯基定理的关系

瓦格纳1937年发表了证明。[1] 库拉托夫斯基以前1930年出版了自己库拉托夫斯基理论[2]

根据该定理,当且仅当图的子图的细分不包含那些禁图K5K3,3

瓦格纳定理意味着库拉托夫斯基,所以是更普遍的。[3]

参考资料

  1. Wagner, K., , Math. Ann., 1937, 114: 570–590, doi:10.1007/BF01594196
  2. Kuratowski, Kazimierz, (PDF), Fund. Math., 1930, 15: 271–283 [2019-04-25], (原始内容 (PDF)存档于2018-07-23) (法语).
  3. Bondy, J. A.; Murty, U.S.R., , Graduate Texts in Mathematics 244, Springer: 269, 2008, ISBN 9781846289699.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.