Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes (Q579241): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Jeffery B. Remmel / 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 | |||
Property / author | |||
Property / author: Jeffery B. Remmel / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0168-0072(86)90051-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2091918101 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective coloration / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursive Euler and Hamilton Paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Countable retracing functions and \(\Pi_2^0\) predicates / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ∏ 0 1 Classes and Degrees of Theories / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degrees of members of \(\Pi_ 1^ 0\) classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Effective Version of Dilworth's Theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursive Colorings of Highly Recursive Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3950561 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A theory of recursive dimension of ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective Matchmaking and k-Chromatic Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Effectiveness of the Schroder-Bernstein Theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5573961 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursive Colorings of Graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:05, 18 June 2024
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