Recursive Colorings of Highly Recursive Graphs

Publisher Website
Google Scholar
Abstract
One of the attractions of finite combinatorics is its explicit constructions. This paper is part of a program to enlarge the domain of finite combinatorics to certain infinite structures while preserving the explicit constructions of the smaller domain. The larger domain to be considered consists of the recursive structures. While recursive structures may be infinite they are still amenable to explicit constructions. In this paper we shall concentrate on recursive colorings of highly recursive graphs.A function f: Nk → N, where N is the set of natural numbers, is recursive if and only if there exists an algorithm (i.e., a finite computer program) which upon input of a sequence of natural numbers , after a finite number of steps, outputs . A subset of Nk is recursive provided that its characteristic function is recursive. For a more thorough definition of recursive functions and recursive relations see [10].

This publication has 0 references indexed in Scilit: