Cover Image

On coarse tree decompositions and coarse balanced separators

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abrishami, Tara, Czyżewska, Jadwiga, Kluk, Kacper, Pilipczuk, Marcin, Pilipczuk, Michał, Rzążewski, Paweł
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
by: Chudnovsky, Maria, et al.
Published: (2024)

Constant congestion brambles in directed graphs
by: Masařík, Tomáš, et al.
Published: (2021)

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

Clique-width and induced topological minors
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

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

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

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

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

Tree-independence number VII. Excluding a star
by: Chudnovsky, Maria, et al.
Published: (2025)

Obstructions and dualities for matroid depth parameters
by: Gajarský, Jakub, et al.
Published: (2025)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

Graph Reconstruction with Connectivity Queries
by: Kluk, Kacper, et al.
Published: (2024)

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

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

Burling graphs in graphs with large chromatic number
by: Abrishami, Tara, et al.
Published: (2025)

Induced matching treewidth and tree-independence number, revisited
by: Alon, Noga, et al.
Published: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

3D-grids are not transducible from planar graphs
by: Gajarský, Jakub, et al.
Published: (2025)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
by: Kluk, Kacper, et al.
Published: (2026)

Tight bound on treedepth in terms of pathwidth and longest path
by: Hatzel, Meike, et al.
Published: (2023)

List coloring ordered graphs with forbidden induced subgraphs
by: Piecyk, Marta, et al.
Published: (2025)

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

A coarse Menger's Theorem for planar and bounded genus graphs
by: Blažej, Václav, et al.
Published: (2026)

Hitting all longest paths in $H$-free graphs and $H$-graphs
by: de Lima, Paloma T., et al.
Published: (2025)

First-order transducibility among classes of sparse graphs
by: Gajarský, Jakub, et al.
Published: (2025)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
by: Bourneuf, Romain, et al.
Published: (2025)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On Computational Aspects of Cores of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

Variants of Merge-Width and Applications
by: Drabik, Karolina, et al.
Published: (2026)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

Graph parameters that are coarsely equivalent to path-length
by: Dragan, Feodor F., et al.
Published: (2025)

Tree-partitions and small-spread tree-decompositions
by: Distel, Marc, et al.
Published: (2026)

Trade-off between spread and width for tree decompositions
by: Bodlaender, Hans L., et al.
Published: (2026)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

Tree-independence number of $P_5$-free graphs with no large bicliques
by: Blažej, Václav, et al.
Published: (2026)