论文标题
本质上四连接的图中的大周期
Large cycles in essentially 4-connected graphs
论文作者
论文摘要
Tutte证明，每个4个连接的平面图都包含汉密尔顿周期，但是有3个连接的$ N $ -VERTEX平面图，其最长的周期具有长度$θ（n^{\ log_32}）$。另一方面，杰克逊（Jackson）和韦尔马德（Wormald）在1992年证明，本质上是4 $ n $ n $ vertex平面图包含一个长度至少$（2n+4）/5 $的周期，最近将其提高到$ 5（n+2）/8 $，由Fabrici {\ it eT al}提高到$ 5（N+2）/8 $。在本文中，我们将其改进为$ \ lceil（2n+6）/3 \ rceil $ for $ n \ ge 6 $，这是最好的，可以通过证明Tutte路径上Thomassen结果的定量版本。
Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but there are 3-connected $n$-vertex planar graphs whose longest cycles have length $Θ(n^{\log_32})$. On the other hand, Jackson and Wormald in 1992 proved that an essentially 4-connected $n$-vertex planar graph contains a cycle of length at least $(2n+4)/5$, which was recently improved to $5(n+2)/8$ by Fabrici {\it et al}. In this paper, we improve this bound to $\lceil (2n+6)/3\rceil$ for $n\ge 6$, which is best possible, by proving a quantitative version of a result of Thomassen on Tutte paths.
