English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Treedepth Vs Circumference

MPS-Authors
/persons/resource/persons255161

Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2211.11410.pdf
(Preprint), 598KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Briański, M., Joret, G., Majewski, K., Micek, P., Seweryn, M. T., & Sharma, R. (2022). Treedepth Vs Circumference. Retrieved from https://arxiv.org/abs/2211.11410.


Cite as: https://hdl.handle.net/21.11116/0000-000C-1E81-1
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 one. 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).