An effective version of Hall’s theorem
HTML articles powered by AMS MathViewer
- by Henry A. Kierstead PDF
- Proc. Amer. Math. Soc. 88 (1983), 124-128 Request permission
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
- Marshall Hall Jr., Distinct representatives of subsets, Bull. Amer. Math. Soc. 54 (1948), 922–926. MR 27033, DOI 10.1090/S0002-9904-1948-09098-X Hall (1935) On representatives of subsets, J. London Math. Soc. 10, 26-30.
- Michael Holz, Klaus-Peter Podewski, and Karsten Steffens, Hall families and the marriage problem, J. Combin. Theory Ser. A 27 (1979), no. 2, 161–180. MR 542526, DOI 10.1016/0097-3165(79)90043-8
- Alfred B. Manaster and Joseph G. Rosenstein, Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall), Proc. London Math. Soc. (3) 25 (1972), 615–654. MR 314610, DOI 10.1112/plms/s3-25.4.615
- Alfred B. Manaster and Joseph G. Rosenstein, Effective matchmaking and $k$-chromatic graphs, Proc. Amer. Math. Soc. 39 (1973), 371–378. MR 340082, DOI 10.1090/S0002-9939-1973-0340082-2
Additional Information
- © Copyright 1983 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 88 (1983), 124-128
- MSC: Primary 03D45; Secondary 05C70
- DOI: https://doi.org/10.1090/S0002-9939-1983-0691291-0
- MathSciNet review: 691291