Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes (Q579241): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Jeffery B. Remmel / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4014694 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
recursive graph | |||
Property / zbMATH Keywords: recursive graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
k-colorings | |||
Property / zbMATH Keywords: k-colorings / rank | |||
Normal rank |
Revision as of 18:23, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes |
scientific article |
Statements
Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes (English)
0 references
1986
0 references
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.
0 references
recursive graph
0 references
k-colorings
0 references