首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Minors in large almost‐5‐connected non‐planar graphs
Authors:Ken‐Ichi Kawarabayashi  John Maharry
Institution:1. National Institute of Informatics, 2‐1‐2, Hitotsubashi Chiyoda‐ku, , Tokyo 101‐8430, Japan;2. Department of Mathematics, Ohio State University, , Columbus, Ohio
Abstract:It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐separations contain a “small” side. As a corollary, every sufficiently large almost‐5‐connected non‐planar graph contains both a K3, 4‐minor and a urn:x-wiley:03649024:jgt20637:equation:jgt20637-math-0001 ‐minor. The connectivity condition cannot be reduced to 4‐connectivity, as there are known infinite families of 4‐connected non‐planar graphs that do not contain a K3, 4‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a urn:x-wiley:03649024:jgt20637:equation:jgt20637-math-0002 ‐minor.
Keywords:minor  5‐connected
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号