Degree Realization with Maximum Matching
cs.DM, cs.DS
Submitted: 2026-10-30
Updated: 2026-10-30
License: http://creativecommons.org/licenses/by/4.0/
The gist: The Maximum Matching Degree Realization problem requires, for a sequence d of n positive integers, to compute a realizing graph(whose degree sequence corresponds to d) with the maximum possible…
Terminology
Abstract
The Maximum Matching Degree Realization problem requires, for a sequence d of n positive integers, to compute a realizing graph(whose degree sequence corresponds to d) with the maximum possible matching. We present a polynomial-time algorithm for this problem. The decision version of this problem requires to determine whether a sequence d admits a realization with a matching of size ν (without computing such a realization). Recently, it was shown that it can be done by verifying a series of inequalities. We improve the existing characterization by reducing the number of inequalities.
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns