Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes

DOI10.1016/0168-0072(86)90051-5zbMath0625.03024OpenAlexW2091918101MaRDI QIDQ579241

Jeffery B. Remmel

Publication date: 1986

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(86)90051-5

zbMATH Keywords

k-coloringsrecursive graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Theory of numerations, effectively presented structures (03D45)

Related Items

Π₀¹-classes and Rado's selection principle, A theory of nonmonotonic rule systems. II, Degrees of orders on torsion-free abelian groups, Graphs are not universal for online computability, Primitive recursive reverse mathematics, A structure of punctual dimension two, Online presentations of finitely generated structures, Recursively presented games and strategies, Countable thin \(\Pi^0_1\) classes, FOUNDATIONS OF ONLINE STRUCTURE THEORY, Index sets for \(\Pi^0_1\) classes, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• A theory of recursive dimension of ordered sets
• Countable retracing functions and \(\Pi_2^0\) predicates
• Degrees of members of \(\Pi_ 1^ 0\) classes
• A decomposition theorem for partially ordered sets
• Recursive Colorings of Highly Recursive Graphs
• An Effective Version of Dilworth's Theorem
• On the Effectiveness of the Schroder-Bernstein Theorem
• Recursive Euler and Hamilton Paths
• Effective coloration
• Recursive Colorings of Graphs
• Effective Matchmaking and k-Chromatic Graphs
• Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
• ∏ 0 1 Classes and Degrees of Theories