Changes
[[File:Unique_match.png]]
A related problem was considered by Golumbic et al.<ref name="GoHi"/>. They showed that in a bipartite graph it is NP-complete to find a matching of maximum size with the property that it is the unique perfect matching of the subgraph induced by its nodes (a ''uniquely restricted matching''). The problem is polynomial-time solvable for interval graphs <ref name="FrJa"/>. In contrast, Penso, Rautenbach, and dos Santos Souza <ref name="PeRa"/> gave a characterization and a polynomial-time recognition algorithm for graphs that have a uniquely restricted maximum matching.
==References==
<ref name="PeRa">L.D. Penso, D. Rautenbach, U. dos Santos Souza, ''Graphs in which some and every maximum matching is uniquely restricted'', [http://arxiv.org/abs/1504.02250 arXiv link]</ref>
<ref name="FrJa">M.C. Francis, D. Jacob, S. Jana, ''Uniquely Restricted Matchings in Interval Graphs'', [http://arxiv.org/abs/1604.07016 arXiv link]
</references>
[[Category:Solved Problems]]
[[Category:Matchings]]
