论文标题
Treedeppth与周长
Treedepth vs circumference
论文作者
论文摘要
图$ g $的周长是$ g $中最长的周期的长度，如果$ g $没有周期，则是$+\ infty $。 Birmelé（2003）表明，图$ g $的树宽最多是其周长$ 1 $。我们以$ 2 $连接的图表来加强此结果：如果$ g $是$ 2 $连接的，则其TreeDeppth最多是其周长。由于Marshall和Wood（2015），该界限是最好的，并且可以改善较早的二次上限。
The circumference of a graph $G$ is the length of a longest cycle in $G$, or $+\infty$ if $G$ has no cycle. Birmelé (2003) showed that the treewidth of a graph $G$ is at most its circumference minus $1$. We strengthen this result for $2$-connected graphs as follows: If $G$ is $2$-connected, then its treedepth is at most its circumference. The bound is best possible and improves on an earlier quadratic upper bound due to Marshall and Wood (2015).
