Recursive coloration of countable graphs

DOI10.1016/0168-0072(83)90052-0MaRDI QIDQ595648zbMATHOpenAlexFDO

Authors Hans-Georg Carstens, Peter Paeppinghaus

Publication date 1983

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(83)90052-0

zbMATH Keywords

recursive graphcellular spacescountably infinite graphseffective version of the theorem of Brooksextensible coloring algorithmrecursive combinatoricstrial and error colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Cites work

• scientific article; zbMATH DE number 3556012 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Effective coloration
• Nonrecursive tilings of the plane. II
• On a system of axioms which has no recursively enumerable arithmetic model
• Π₁⁰ classes and Boolean combinations of recursively enumerable sets

Cited in

(7)

• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• \(A\)-computable graphs
• The Mapmaker's dilemma
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Computing planarity in computable planar graphs
• The online graph bandwidth problem
• On the finiteness of the recursive chromatic number

This page was built for publication: Recursive coloration of countable graphs

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