Factorially many maximum matchings close to the Erdős-Gallai bound

DOI10.37236/10610zbMath1492.05125arXiv2108.00134OpenAlexW4282968460WikidataQ114023888 ScholiaQ114023888MaRDI QIDQ2152791

Dieter Rautenbach, L. Picasarri-Arrieta, Johannes Pardey, Stéphane Bessy

Publication date: 11 July 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.00134

zbMATH Keywords

matching numbermaximum matchings

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Exponentially many perfect matchings in cubic graphs
• The complexity of computing the permanent
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
• Matching theory
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• The solution of van der Waerden's problem for permanents
• On maximal paths and circuits of graphs

This page was built for publication: Factorially many maximum matchings close to the Erdős-Gallai bound