Back to Search
Start Over
Treedepth vs circumference
- 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
- Subjects :
- Mathematics - Combinatorics
Computer Science - Discrete Mathematics
Subjects
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