Degree Realization with Maximum Matching

arXiv:2610.41810 · cs.DM, cs.DS · Submitted 2026-10-30 · Read on arXiv

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