Cover Image

On the complexity of Sandwich Problems for $M$-partitions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Barsukov, Alexey, Guzmán-Pro, Santiago
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Discrete Mathematics Combinatorics 05C15, 05C60 G.2.2; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A CSP approach to Graph Sandwich Problems
by: Bodirsky, Manuel, et al.
Published: (2025)

GMSNP and Finite Structures
by: Guzmán-Pro, Santiago
Published: (2024)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

On λ-backbone coloring of cliques with tree backbones in linear time
by: Michalik, Krzysztof, et al.
Published: (2021)

Some Thoughts on Graph Similarity
by: Grohe, Martin
Published: (2024)

On Strict Brambles
by: Lardas, Emmanouil, et al.
Published: (2022)

On Brooks' Theorem
by: Sajith, Gopalan, et al.
Published: (2022)

Reuniting $χ$-boundedness with polynomial $χ$-boundedness
by: Chudnovsky, Maria, et al.
Published: (2023)

Fractional Chromatic Numbers from Exact Decision Diagrams
by: Brand, Timo, et al.
Published: (2024)

Variants of the Gyàrfàs-Sumner Conjecture: Oriented Trees and Rainbow Paths
by: Basavaraju, Manu, et al.
Published: (2021)

Extension property for partial automorphisms of the $n$-partite and semigeneric tournaments
by: Hubička, Jan, et al.
Published: (2024)

Compact Representation of Semilinear and Terrain-like Graphs
by: Cardinal, Jean, et al.
Published: (2025)

The classification of minimally unsatisfiable 2-CNFs -- a fundamental study
by: Abbasizanjani, Hoda, et al.
Published: (2020)

Dichromatic Number and Cycle Inversions
by: Charbit, Pierre, et al.
Published: (2024)

Coloring Graphs With No Totally Odd Clique Immersion
by: McFarland, Caleb
Published: (2025)

Graphs without a 3-connected subgraph are 4-colorable
by: Bonnet, Édouard, et al.
Published: (2024)

On Chollet's Permanent Conjecture for Graph Laplacians
by: Pant, Priyanshu, et al.
Published: (2026)

Edge-coloring problems with forbidden patterns and planted colors
by: Barsukov, Alexey, et al.
Published: (2025)

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

On the Alon-Tarsi Number of Some Line and Total graphs
by: Prajnanaswaroopa, S.
Published: (2023)

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

A new density limit for unanimity in majority dynamics on random graphs
by: Kim, Jeong Han, et al.
Published: (2025)

Complexity of Firefighting on Graphs
by: Althoetmar, Julius, et al.
Published: (2025)

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

Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs
by: De Meyer, Lucas
Published: (2025)

Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles
by: Benevides, Fabrício Siqueira, et al.
Published: (2024)

Computing a 3-role assignment is polynomial-time solvable on complementary prisms
by: Castonguay, Diane, et al.
Published: (2024)

The Gallai Vertex Problem is $Θ_2^p$-Complete
by: Nikabadi, Amir, et al.
Published: (2026)

Permanental Energy of Graphs
by: Pant, Priyanshu, et al.
Published: (2026)

Conflict-Free Colouring of Subsets
by: Jartoux, Bruno, et al.
Published: (2022)

On roots of domination polynomials for friendship and book graphs
by: Rather, Bilal Ahmad
Published: (2026)

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

The steady-states of splitter networks
by: Couëtoux, Basile, et al.
Published: (2024)

Models of random spanning trees
by: Babson, Eric, et al.
Published: (2024)

The bunkbed conjecture is false
by: Gladkov, Nikita, et al.
Published: (2024)

Independent Set Enumeration in King Graphs by Tensor Network Contractions
by: Liang, Kai
Published: (2025)

Completely independent spanning trees in the hypercube
by: Shaw, Benedict Randall
Published: (2024)

Directed branch-width: A directed analogue of tree-width
by: Bumpus, Benjamin Merlin, et al.
Published: (2020)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

Graph Parameters, Universal Obstructions, and WQO
by: Paul, Christophe, et al.
Published: (2023)