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 Free Access

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?)

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