Recursive coloration of countable graphs

DOI10.1016/0168-0072(83)90052-0zbMath0527.03025OpenAlexW2008839847MaRDI QIDQ595648

Peter Paeppinghaus, Hans-Georg Carstens

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)

Related Items (7)

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

Cites Work

• Nonrecursive tilings of the plane. II
• Effective coloration
• Π₁⁰ classes and Boolean combinations of recursively enumerable sets
• On a system of axioms which has no recursively enumerable arithmetic model
• Unnamed Item
• Unnamed Item
• Unnamed Item

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