Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



An effective version of Hall's theorem

Author: Henry A. Kierstead
Journal: Proc. Amer. Math. Soc. 88 (1983), 124-128
MSC: Primary 03D45; Secondary 05C70
MathSciNet review: 691291
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

  • [M] Hall (1948) Distinct representatives of subsets, Bull. Amer. Math. Soc. 54, 922-926. MR 0027033 (10:238g)
  • [P] Hall (1935) On representatives of subsets, J. London Math. Soc. 10, 26-30.
  • [M] Holz, K.-P. Podewski and K. Steffens (1979) Hall families and the marriage problem, J. Combinatorial Theory Ser. A 27, 161-180. MR 542526 (81e:04005)
  • [A] Manaster and J. Rosenstein (1972) Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall), Proc. London Math. Soc. 25, 615-654. MR 0314610 (47:3161)
  • 1. -(1973) Effective matchmaking and $ k$-chromatic graphs, Proc. Amer. Math. Soc. 39, 371-378. MR 0340082 (49:4838)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03D45, 05C70

Retrieve articles in all journals with MSC: 03D45, 05C70

Additional Information

Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society