Cycles in 4-connected planar graphs
Cycles in 4-connected planar graphs
复制标题
4 连通平面图中的循环
DOI：
10.1016/j.ejc.2003.04.003
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Xingxing Yu
中科院分区：
文献类型：
--
作者：
Guantao Chen;G. Fan;Xingxing Yu
设G是n阶4连通平面图。已有的结果表明，对任意k∈{n，n−1，n−2，n−3}，G包含一个长为k的圈，其中k≥3。这些结果证明使用“Tutte路径”技术，这种技术不能单独使用，以获得进一步的结果在这个方向上。获得进一步结果的一种方法是将Tutte路径和可收缩边组合联合收割机。在本文中，我们证明了这种方法，通过证明G也有一个长度为k的圈，对每个k∈{n−4，n−5，n−6}，k≥3。这项工作的部分动机是旧猜想Malkevitch。
Let G be a 4-connected planar graph on n vertices. Previous results show that G contains a cycle of length k for each k∈{n,n−1,n−2,n−3} with k≥3. These results are proved using the “Tutte path” technique, and this technique alone cannot be used to obtain further results in this direction. One approach to obtain further results is to combine Tutte paths and contractible edges. In this paper, we demonstrate this approach by showing that G also has a cycle of length k for each k∈{n−4,n−5,n−6} with k≥3. This work was partially motivated by an old conjecture of Malkevitch.