Cover Image

On the Complexity of Bipartite Degree Realizability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Miklós, István
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Computational Complexity 05C07, 05C85, 68Q25
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A dichotomy theorem on the complexity of 3-uniform hypergraphic degree sequence graphicality
by: Logsdon, Sara, et al.
Published: (2024)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

The Mutual-Visibility Problem In Directed Graphs
by: Stojanović, Vanja
Published: (2026)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

Integral Biflow Maximization
by: Ding, Guoli, et al.
Published: (2024)

Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets
by: Grippo, Luciano N., et al.
Published: (2025)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
by: Ameli, Afrouz Jabal, et al.
Published: (2024)

A Linear Kernel for Independent Set Reconfiguration in Planar Graphs
by: Bousquet, Nicolas, et al.
Published: (2025)

Degree Realization by Bipartite Multigraphs
by: Bar-Noy, Amotz, et al.
Published: (2025)

More algorithmic results for problems of spread of influence in edge-weighted graphs with and without incentives
by: Askari, Siavash, et al.
Published: (2024)

Graphs whose vertices of degree at least 2 lie in a triangle
by: Forte, Vinicius L. do, et al.
Published: (2022)

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

On balanceable and simply balanceable regular graphs
by: Ahanjideh, Milad, et al.
Published: (2024)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Edge open packing: complexity, algorithmic aspects, and bounds
by: Brešar, Boštjan, et al.
Published: (2024)

Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs
by: Jaworska, Justyna, et al.
Published: (2025)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors
by: Gollin, J. Pascal, et al.
Published: (2023)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

The General Position Problem: A Survey
by: V., Ullas Chandran S., et al.
Published: (2025)

Lower General Position Sets in Graphs
by: Di Stefano, Gabriele, et al.
Published: (2023)

Tight complexity bounds for diagram commutativity verification
by: Malko, Artem, et al.
Published: (2025)

Computational methods for finding bi-regular cages
by: Goedgebeur, Jan, et al.
Published: (2024)

Complexity of Sequence-to-Graph Alignment with Co-Linear Chaining
by: Li, Xingfu
Published: (2026)

The maximum number of connected sets in regular graphs
by: Cambie, Stijn, et al.
Published: (2023)

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
by: Galby, Esther, et al.
Published: (2024)

A Graph-based Framework for Coverage Analysis in Autonomous Driving
by: Muehlenstädt, Thomas, et al.
Published: (2026)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
by: Hoang, Duc A.
Published: (2022)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

On 3-colorability of (claw, diamond)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2026)

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

Corrigendum to "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3]
by: Dourado, Mitre C., et al.
Published: (2023)

On the joint embedding property for cographs and trees
by: Carter, Daniel
Published: (2024)

Approximating branchwidth on parametric extensions of planarity
by: Thilikos, Dimitrios M., et al.
Published: (2023)

Realizations and Uniqueness of Cut Complexes of Graphs
by: Shen, Yufeng, et al.
Published: (2025)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

On $\{k\}$-Roman graphs: complexity of recognition and the case of split graphs
by: Štorgel, Kenny Bešter, et al.
Published: (2025)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
by: Goedgebeur, Jan, et al.
Published: (2024)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)