K_7-Minors in optimal 1-planar graphs
K_7-Minors in optimal 1-planar graphs
复制标题
最优 1 平面图中的 K_7-Minors
DOI：
10.1016/j.disc.2017.01.022
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
Yusuke Suzuki
中科院分区：
文献类型：
--
作者：
Nishina Makoto;Suzuki Yusuke;鈴木信行;鈴木信行;Yusuke Suzuki
讨论了最优1-平面图中给定图的子式的存在性。作为我们的第一个主要结果，我们证明了对于任何图H，存在一个最优1-平面图，它包含H作为拓扑子式。接下来，我们考虑完全图的子图。从马德尔（马德尔，1968）的结果可以很容易地得到：每个最优1-平面图都有一个K6-子式.本文刻画了不含K7-子式的最优1-平面图.
We discuss the existence of minors of given graphs in optimal 1-planar graphs. As our first main result, we prove that for any graph H, there exists an optimal 1-planar graph which contains H as a topological minor. Next, we consider minors of complete graphs. It is easily obtained from Mader’s result (Mader, 1968) that every optimal 1-planar graph has a K 6-minor. In the paper, we characterize optimal 1-planar graphs having no K 7-minor.