Effective matchmaking and $k$-chromatic graphs

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.