A-computable graphs

DOI10.1016/J.APAL.2015.11.003MaRDI QIDQ904145zbMATH OpenOpenAlexFDO

Authors Matthew Jura, Oscar Levin, Tyler Markkanen

Publication date 12 January 2016

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

Full work available at URL https://doi.org/10.1016/j.apal.2015.11.003

zbMATH Keywords

chromatic numbercomputability theoryEuler pathshighly computable graphs

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Recommendations

• On the finiteness of the recursive chromatic number
• Domatic partitions of computable graphs
• Computing planarity in computable planar graphs
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

Cites work

• A minimal degree not realizing least possible jump
• Computability and randomness
• Degrees of Unsolvability. (AM-55)
• Domatic partitions of computable graphs
• Effective coloration
• Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
• Hamiltonian paths in infinite graphs
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• Initial segments of the degrees of unsolvability Part II: minimal degrees
• On the finiteness of the recursive chromatic number
• Recursive coloration of countable graphs
• Recursive Colorings of Graphs
• Recursive Colorings of Highly Recursive Graphs
• Recursive Euler and Hamilton Paths
• The _2⁰-spectrum of a linear order

Cited in

(1)

• Computing planarity in computable planar graphs

This page was built for publication: \(A\)-computable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q904145)