English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Treedepth Vs Circumference

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.

Item is

Files

show Files
hide Files
:
arXiv:2211.11410.pdf (Preprint), 598KB
Name:
arXiv:2211.11410.pdf
Description:
File downloaded from arXiv at 2023-01-04 10:07
OA-Status:
Green
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Briański, Marcin1, Author
Joret, Gwenaël1, Author
Majewski, Konrad1, Author
Micek, Piotr1, Author
Seweryn, Michał T.1, Author
Sharma, Roohani2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM
 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).

Details

show
hide
Language(s): eng - English
 Dates: 2022-11-212022-11-222022
 Publication Status: Published online
 Pages: 4 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2211.11410
BibTex Citekey: Brianski2211.11410
URI: https://arxiv.org/abs/2211.11410
 Degree: -

Event

show

Legal Case

show

Project information

show hide
Project name : BOBR
Grant ID : 948057
Funding program : Horizon 2020 (H2020)
Funding organization : European Commission (EC)

Source

show