Cover Image

Tight bound on treedepth in terms of pathwidth and longest path

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hatzel, Meike, Joret, Gwenaël, Micek, Piotr, Pilipczuk, Marcin, Ueckerdt, Torsten, Walczak, Bartosz
Format:	Preprint
Published:	2023
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Cliquewidth and dimension
by: Joret, Gwenaël, et al.
Published: (2023)

Tight bound for the Erdős-Pósa property of tree minors
by: Dujmović, Vida, et al.
Published: (2024)

Note on the treewidth of graphs excluding a disjoint union of cycles as a minor
by: Joret, Gwenaël, et al.
Published: (2026)

On graphs coverable by chubby shortest paths
by: Hatzel, Meike, et al.
Published: (2025)

Tree decompositions whose trees are subgraphs: An application of Simon's factorization
by: Bourneuf, Romain, et al.
Published: (2026)

Erdős--Pósa property of cycles that are far apart
by: Dujmović, Vida, et al.
Published: (2024)

Cops and robber in graphs with bounded vertex cover number
by: Bose, Prosenjit, et al.
Published: (2026)

Erdős-Pósa property of tripods in directed graphs
by: Briański, Marcin, et al.
Published: (2024)

Half-integral Erdős-Pósa property for non-null $S$-$T$ paths
by: Chekan, Vera, et al.
Published: (2024)

A Caro-Wei bound for induced linear forests in graphs
by: Joret, Gwenaël, et al.
Published: (2024)

Odd coloring graphs with linear neighborhood complexity
by: Davies, James, et al.
Published: (2025)

The Excluded Tree Minor Theorem Revisited
by: Dujmović, Vida, et al.
Published: (2023)

Planar graphs in blowups of fans
by: Distel, Marc, et al.
Published: (2024)

Adjacency labelling for proper minor-closed graph classes
by: Dujmović, Vida, et al.
Published: (2026)

Pathwidth vs cocircumference
by: Briański, Marcin, et al.
Published: (2023)

Clustered independence and bounded treewidth
by: Knauer, Kolja, et al.
Published: (2023)

Neighborhood complexity of planar graphs
by: Joret, Gwenaël, et al.
Published: (2023)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
by: Pilipczuk, Marcin, et al.
Published: (2023)

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths
by: Baste, Julien, et al.
Published: (2025)

A Note on Polychromatic Colorings of Shift-Chains
by: Ueckerdt, Torsten
Published: (2024)

Computing $\vec{\mathcal{S}}$-DAGs and Parity Games
by: Hatzel, Meike, et al.
Published: (2024)

Improved lower bounds on the maximum size of graphs with girth 5
by: Goedgebeur, Jan, et al.
Published: (2025)

Blow-up structure of graphs excluding a tree or an apex-tree as a minor
by: Claus, Quentin, et al.
Published: (2026)

Cliquewidth and dimension
by: Gwenaël Joret, et al.
Published: (2026)

Directed treewidth is closed under taking butterfly minors
by: Kim, Gunwoo, et al.
Published: (2025)

Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods
by: Schneider, Samuel, et al.
Published: (2025)

The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number
by: Goetze, Miriam, et al.
Published: (2025)

Excluding an apex-forest or a fan as quickly as possible
by: Claus, Quentin, et al.
Published: (2026)

Strong odd colorings in graph classes of bounded expansion
by: Pilipczuk, Michał
Published: (2025)

On graphs with a simple structure of maximal cliques
by: Gollin, J. Pascal, et al.
Published: (2025)

Polynomial-time recognition and maximum independent set in Burling graphs
by: Rzążewski, Paweł, et al.
Published: (2024)

The treewidth and pathwidth of graph unions
by: Alecu, Bogdan, et al.
Published: (2022)

Non-empty intersection of longest paths in $H$-free graphs
by: Long Jr., James A., et al.
Published: (2023)

Cops and Robber -- When Capturing is not Surrounding
by: Jungeblut, Paul, et al.
Published: (2023)

Boundedness and Separation in the Graph Covering Number Framework
by: Goetze, Miriam, et al.
Published: (2025)

Directed Acyclic Outerplanar Graphs Have Constant Stack Number
by: Jungeblut, Paul, et al.
Published: (2022)

Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs
by: Goetze, Miriam, et al.
Published: (2024)

Edge densities of drawings of graphs with one forbidden cell
by: Hahn, Benedikt, et al.
Published: (2025)

Partitioning a Planar Graph into two Triangle-Forests
by: Knauer, Kolja, et al.
Published: (2024)

Tree-partitions of graphs with given pathwidth
by: Wood, David R.
Published: (2026)