Long cycles in 4-connected planar graphs |
| |
Authors: | Qing Cui Yumei Hu Jian Wang |
| |
Affiliation: | a Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin 300071, PR China b Department of Mathematics, Tianjin University, Tianjin 300072, PR China |
| |
Abstract: | Let G be a 4-connected planar graph on n vertices. Malkevitch conjectured that if G contains a cycle of length 4, then G contains a cycle of length k for every k∈{n,n−1,…,3}. This conjecture is true for every k∈{n,n−1,…,n−6} with k≥3. In this paper, we prove that G also has a cycle of length n−7 provided n≥10. |
| |
Keywords: | Hamilton cycle Tutte path Contractible subgraph |
本文献已被 ScienceDirect 等数据库收录! |
|