Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes (Q579241): Difference between revisions

Bean showed that the k-colorings of a recursive graph is always a recursively bounded \(\Pi^ 0_ 1\)-class. The main theorem of this paper proves the converse of Bean's result. That is, we show that for any recursively bounded \(\Pi^ 0_ 1\)-class \({\mathcal C}\) and any \(k\geq 3\), there exists a highly recursive graph \({\mathcal G}\) such that up to a permutation of colors there is an effective 1:1 degree preserving correspondence between the k-colorings of \({\mathcal G}\) and the elements of \({\mathcal C}\). We also discuss other combinatorial problems whose solutions are recursively bounded \(\Pi^ 0_ 1\)-classes and the possibility of their representing an arbitrary \(\Pi^ 0_ 1\)-class.