科研之友
微信
新浪微博
Facebook
分享链接
摘要
Jackson and Wormald conjecture that if G is a 3-connected n-vertex graph with maximum degree d >= 4, then G has a cycle of length Omega(n(logd-1 2)). We show that this conjecture holds when d - 1 is replaced by max{64, 4d + 1}. Our proof implies a cubic algorithm for finding such a cycle.
