加载中…
The circumference of a graph is the length of a longest cycle in , or if has no cycle. Birmelé (2003) showed that the treewidth of a graph is at most its circumference minus . We strengthen this result for -connected graphs as follows: If is -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).

生成讲解博客的中文版本

生成AI智能校验的中文版本