Recursive coloration of countable graphs

DOI10.1016/0168-0072(83)90052-0zbMATH Open0527.03025OpenAlexW2008839847MaRDI QIDQ595648FDOQ595648

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Effective coloration
• Nonrecursive tilings of the plane. II
• Title not available (Why is that?)
• Π₁⁰ classes and Boolean combinations of recursively enumerable sets
• On a system of axioms which has no recursively enumerable arithmetic model

Cited In (7)

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

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)