ON CATEGORICITY SPECTRA FOR LOCALLY FINITE GRAPHS

Under study is the algorithmic complexity of isomorphisms between computable copies of locally finite graphs G (undirected graphs whose every vertex has finite degree). We obtain the following results: If G has only finitely many components then G is d-computably categorical for every Turing degree d from the class PA(0'). If G has infinitely many components then G is 0 ''-computably categorical. We exhibit a series of examples showing that the obtained bounds are sharp.