Cover Image

Sparse Induced Subgraphs of Large Treewidth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Bonnet, Édouard
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Discrete Mathematics Data Structures and Algorithms 05C99, 05C69 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

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

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

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

On Relaxation of Dominant Sets
by: Koster, Max
Published: (2022)

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

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

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

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

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

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

Isolation critical graphs under multiple edge subdivision
by: Bartolo, Karl, et al.
Published: (2026)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
by: Dallard, Clément, et al.
Published: (2024)

An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
by: De Meyer, Lucas, et al.
Published: (2025)

Explicit Formulas and Unimodality Phenomena for General Position Polynomials
by: Rather, Bilal Ahmad
Published: (2026)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets
by: Enami, Kengo, et al.
Published: (2025)

Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
by: Chimani, Markus, et al.
Published: (2023)

Flip-width: Cops and Robber on dense graphs
by: Toruńczyk, Szymon
Published: (2023)

Resolving Sets in Temporal Graphs
by: Bok, Jan, et al.
Published: (2024)

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
by: Gartland, Peter, et al.
Published: (2023)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

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

A simple quadratic kernel for Token Jumping on surfaces
by: Cranston, Daniel W., et al.
Published: (2024)

Vertex connectivity of the nonzero nonunit core of the comaximal graph of $\mathbb Z_n$
by: Rather, Bilal Ahmad
Published: (2026)

Geometric realizations of dichotomous ordinal graphs
by: Angelini, Patrizio, et al.
Published: (2025)

List Coloring of some Cayley graphs using Kernel perfections
by: S, Prajnanaswaroopa
Published: (2024)

Alon-Tarsi Number of Some Regular Graphs
by: Prajnanaswaroopa, S.
Published: (2023)

Approximating the volume of a truncated relaxation of the independence polytope
by: Bencs, Ferenc, et al.
Published: (2024)

Secure Total Domination Number in Maximal Outerplanar Graphs
by: Aita, Yasufumi, et al.
Published: (2024)

A Lower bound for Secure Domination Number of an Outerplanar Graph
by: Araki, Toru
Published: (2024)

Recognizing Relating Edges in Graphs without Cycles of Length 6
by: Levit, Vadim E., et al.
Published: (2024)

Domination and packing in graphs
by: Gómez, Renzo, et al.
Published: (2024)

Quasi-kernels in split graphs
by: Langlois, Hélène, et al.
Published: (2023)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

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

Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm
by: Klein, Kim-Manuel, et al.
Published: (2024)

Graphs with core(G) = nucleus(G)
by: Levit, Vadim E., et al.
Published: (2026)