Copertina

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bonnet, Édouard, Hodor, Jędrzej, Korhonen, Tuukka, Masařík, Tomáš
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Combinatorics Discrete Mathematics Data Structures and Algorithms 05C83 G.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Excluding a Forest Induced Minor
di: Bonnet, Édouard, et al.
Pubblicazione: (2025)

Sparse Induced Subgraphs of Large Treewidth
di: Bonnet, Édouard
Pubblicazione: (2024)

Treewidth Inapproximability and Tight ETH Lower Bound
di: Bonnet, Édouard
Pubblicazione: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
di: Korhonen, Tuukka, et al.
Pubblicazione: (2024)

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

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Coloring Hardness on Low Twin-Width Graphs
di: Bonnet, Édouard
Pubblicazione: (2025)

Separator Theorem for Minor-Free Graphs in Linear Time
di: Bonnet, Édouard, et al.
Pubblicazione: (2025)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
di: Bonnet, Édouard, et al.
Pubblicazione: (2023)

Answering Related Questions
di: Bonnet, Édouard
Pubblicazione: (2025)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
di: Neuen, Daniel
Pubblicazione: (2020)

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
di: Masařík, Tomáš, et al.
Pubblicazione: (2026)

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
di: Cook, Linda, et al.
Pubblicazione: (2025)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
di: Deligkas, Argyrios, et al.
Pubblicazione: (2025)

Mim-Width is paraNP-complete
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
di: Bourneuf, Romain, et al.
Pubblicazione: (2025)

Moderately beyond clique-width: reduced component max-leaf and related parameters
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Induced Minors and Coarse Tree Decompositions
di: Chudnovsky, Maria, et al.
Pubblicazione: (2026)

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

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

Finding Diverse Solutions Parameterized by Cliquewidth
di: Drabik, Karolina, et al.
Pubblicazione: (2024)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

Every Graph is Essential to Large Treewidth
di: Alecu, Bogdan, et al.
Pubblicazione: (2025)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
di: Dhawan, Abhishek
Pubblicazione: (2024)

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
di: Choi, Mujin, et al.
Pubblicazione: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
di: Beisegel, Jesse, et al.
Pubblicazione: (2025)

Stability in Graphs with Matroid Constraints
di: Fomin, Fedor V., et al.
Pubblicazione: (2024)

Dynamic Treewidth in Logarithmic Time
di: Korhonen, Tuukka
Pubblicazione: (2025)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
di: Korhonen, Tuukka
Pubblicazione: (2024)

Lower Bounds for Leaf Rank of Leaf Powers
di: Høgemo, Svein
Pubblicazione: (2024)

Computing parameters that generalize interval graphs using restricted modular partitions
di: Bonomo-Braberman, Flavia, et al.
Pubblicazione: (2025)

Optimal distance query reconstruction for graphs without long induced cycles
di: Bastide, Paul, et al.
Pubblicazione: (2023)

Minor Containment and Disjoint Paths in almost-linear time
di: Korhonen, Tuukka, et al.
Pubblicazione: (2024)

Colorful Minors
di: Protopapas, Evangelos, et al.
Pubblicazione: (2025)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
di: MacRury, Calum, et al.
Pubblicazione: (2022)

Symmetric-Difference (Degeneracy) and Signed Tree Models
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

Random Schreier graphs as expanders
di: Caillat-Grenier, Geoffroy
Pubblicazione: (2023)

SSD Set System, Graph Decomposition and Hamiltonian Cycle
di: Shota, Kan, et al.
Pubblicazione: (2024)

Structural and Combinatorial Properties of 2-swap Word Permutation Graphs
di: Adamson, Duncan, et al.
Pubblicazione: (2023)