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)



Effective matchmaking and $ k$-chromatic graphs

Authors: Alfred B. Manaster and Joseph G. Rosenstein
Journal: Proc. Amer. Math. Soc. 39 (1973), 371-378
MSC: Primary 05C15; Secondary 02F50
MathSciNet review: 0340082
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In an earlier paper we showed that there is a recursive society, in which each person knows exactly two other people, whose marriage problem is solvable but not recursively solvable. We generalize this result, using a different construction, to the case where each person knows exactly $ k$ other people. From this we deduce that for each $ k \geqq 2$ there is a recursive $ 2(k - 1)$-regular graph, whose chromatic number is $ k$ but which is not recursively $ k$ chromatic.

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

  • [1] Claude Berge, The theory of graphs and its applications, Methuen, London; Wiley, New York, 1962. MR 24 #A2381. MR 0132541 (24:A2381)
  • [2] A. B. Manaster and J. G. Rosenstein, Effective matchmaking (Recursion theoretic aspects of a theorem of Phillip Hall), Proc. London Math. Soc. (3) 25 (1972), 615-654. MR 0314610 (47:3161)
  • [3] P. Halmos and H. Vaughan, The marriage problem, Amer. J. Math. 72 (1950), 214-215. MR 11, 423. MR 0033330 (11:423h)
  • [4] L. Mirsky, Transversal theory, Academic Press, New York, 1971. MR 0282853 (44:87)
  • [5] Hartley Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C15, 02F50

Retrieve articles in all journals with MSC: 05C15, 02F50

Additional Information

Keywords: Bipartite graph, $ k$-regular graph, chromatic number, matching, marriage problem, algorithm, recursive function
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society