%0 Generic %1 chaplick2017graphs %A Chaplick, S. %A Fürst, M. %A Maffray, F. %A Rautenbach, D. %D 2017 %K arxiv myown %T On some Graphs with a Unique Perfect Matching %U http://arxiv.org/abs/1712.04228 %X We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O(m)$ if $G$ is either a cograph, or a split graph, or an interval graph, or claw-free. Furthermore, we provide a constructive characterization of the claw-free graphs with a unique perfect matching.

@misc{chaplick2017graphs, abstract = {We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O(m)$ if $G$ is either a cograph, or a split graph, or an interval graph, or claw-free. Furthermore, we provide a constructive characterization of the claw-free graphs with a unique perfect matching.}, added-at = {2018-07-25T14:42:33.000+0200}, author = {Chaplick, S. and Fürst, M. and Maffray, F. and Rautenbach, D.}, biburl = {https://www.bibsonomy.org/bibtex/2bd2ea9ba47b2713606d78690543fe659/chaplick}, description = {[1712.04228] On some Graphs with a Unique Perfect Matching}, interhash = {6ff17b282954f0be16bdf96a292673c0}, intrahash = {bd2ea9ba47b2713606d78690543fe659}, keywords = {arxiv myown}, note = {cite arxiv:1712.04228}, timestamp = {2018-07-25T14:42:33.000+0200}, title = {On some Graphs with a Unique Perfect Matching}, url = {http://arxiv.org/abs/1712.04228}, year = 2017 }