| Autor: |
Briański, M., Joret, G., Majewski, K., Micek, P., Seweryn, M., Sharma, R. |
| Jazyk: |
angličtina |
| Rok vydání: |
2022 |
| Popis: |
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 agraph $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 isat most its circumference. The bound is best possible and improves on anearlier quadratic upper bound due to Marshall and Wood (2015). |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
