Cover Image

Sandwich Monotonicity and the Recognition of Weighted Graph Classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Beisegel, Jesse, Chiarelli, Nina, Köhler, Ekkehard, Krnc, Matjaž, Milanič, Martin, Pivač, Nevena, Scheffler, Robert, Strehler, Martin
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Graph Search Trees and the Intermezzo Problem
by: Beisegel, Jesse, et al.
Published: (2024)

Breadth-First Search Trees with Many or Few Leaves
by: Beisegel, Jesse, et al.
Published: (2026)

Computing Hamiltonian Paths with Partial Order Restrictions
by: Beisegel, Jesse, et al.
Published: (2024)

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

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

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
by: Milanič, Martin, et al.
Published: (2024)

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

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

Graph Classes Closed under Self-intersection
by: Dabrowski, Konrad K., et al.
Published: (2025)

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

Young domination on Hamming rectangles
by: Gravner, Janko, et al.
Published: (2025)

On constrained intersection representations of graphs and digraphs
by: Cicalese, Ferdinando, et al.
Published: (2025)

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
by: Scheffler, Robert
Published: (2025)

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

Linear colorings of graphs
by: Hilaire, Claire, et al.
Published: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

Twin-width one
by: Ahn, Jungho, et al.
Published: (2025)

Sampling Tree-Weighted Partitions Without Sampling Trees
by: Cannon, Sarah, et al.
Published: (2025)

Greedy Gray Codes for some Restricted Classes of Binary Words
by: Hassler, Nathanaël, et al.
Published: (2024)

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

Interval H-graphs : Recognition and forbidden obstructions
by: Müller, Haiko, et al.
Published: (2025)

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

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

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
by: Charbit, Pierre, et al.
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)

Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join
by: Kita, Nanano
Published: (2025)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

$α_i$-Metric Graphs: Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

Colouring Probe $H$-Free Graphs
by: Paulusma, Daniël, et al.
Published: (2025)

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

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

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

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
by: Holtgrefe, Niels, et al.
Published: (2024)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

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

A Faster Isomorphism Test for Graphs of Small Degree
by: Grohe, Martin, et al.
Published: (2018)