An effective version of Hall’s theorem
- 1 May 1983
- journal article
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 88 (1) , 124-128
- https://doi.org/10.1090/s0002-9939-1983-0691291-0
Abstract
Manaster and Rosenstein [1972] constructed a recursively bipartite highly recursive graph that satisfies Hall’s condition for a bipartite graph to have a matching, but has no recursive matching. We discuss a natural extension of Hall’s condition which assures that every such graph has a recursive matching.Keywords
This publication has 5 references indexed in Scilit:
- Hall families and the marriage problemJournal of Combinatorial Theory, Series A, 1979
- Effective Matchmaking and k-Chromatic GraphsProceedings of the American Mathematical Society, 1973
- Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)Proceedings of the London Mathematical Society, 1972
- Distinct representatives of subsetsBulletin of the American Mathematical Society, 1948
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935