Back to Search Start Over

Treedepth vs circumference

Authors :
Briański, Marcin
Joret, Gwenaël
Majewski, Konrad
Micek, Piotr
Seweryn, Michał T.
Sharma, Roohani
Source :
Combinatorica, 43:659--664, 2023
Publication Year :
2022

Abstract

The circumference of a graph $G$ is the length of a longest cycle in $G$, or $+\infty$ if $G$ has no cycle. Birmel\'e (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).<br />Comment: v3: Revised following the referees's comments

Details

Database :
arXiv
Journal :
Combinatorica, 43:659--664, 2023
Publication Type :
Report
Accession number :
edsarx.2211.11410
Document Type :
Working Paper
Full Text :
https://doi.org/10.1007/s00493-023-00028-5