Cover Image

Variants of Merge-Width and Applications

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Drabik, Karolina, Dumas, Maël, Geniet, Colin, Nowakowski, Jakub, Pilipczuk, Michał, Toruńczyk, Szymon
Format:	Preprint
Published:	2026
Subjects:	Combinatorics Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Flips and Merge-Width in Sparse Graphs
by: Drabik, Karolina, et al.
Published: (2026)

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

Merge-width and First-Order Model Checking
by: Dreier, Jan, et al.
Published: (2025)

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

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

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

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)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors
by: Dallard, Clément, et al.
Published: (2024)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

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

On multidimensional generalization of binary search
by: Dereniowski, Dariusz, et al.
Published: (2024)

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

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

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

Solving Problems on Generalized Convex Graphs via Mim-Width
by: Bonomo-Braberman, Flavia, et al.
Published: (2020)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
by: Beisegel, Jesse, et al.
Published: (2025)

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
by: Beisegel, Jesse, et al.
Published: (2024)

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)

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

$χ$-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
by: Beisegel, Jesse, et al.
Published: (2025)

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

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

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)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
by: Bedert, Benjamin, et al.
Published: (2025)

Vigemers: on the number of $k$-mers sharing the same XOR-based minimizer
by: Ingels, Florian, et al.
Published: (2026)

Induced Cycles of Many Lengths
by: Chudnovsky, Maria, et al.
Published: (2026)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Unsplittable Transshipments
by: Debgupta, Srinwanti, et al.
Published: (2026)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

Generating minimal redundant and maximal irredundant sets in incidence graphs
by: Castelo, Emanuel, et al.
Published: (2026)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

EPTAS for Hard Graph Cut Problems for Dense Graphs
by: Deguchi, Kaisei, et al.
Published: (2026)

Hardness of Burning Number Problem on Regular Graphs
by: Antony, Dhanyamol, et al.
Published: (2026)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
by: Avila, Tatiana Rocha, et al.
Published: (2026)

The Complexity of Homomorphism Reconstruction Revisited
by: Gervens, Timo, et al.
Published: (2026)

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

Designing sparse temporal graphs satisfying connectivity requirements
by: Bellitto, Thomas, et al.
Published: (2026)