k-Colorability is Graph Automaton Recognizable

Abstract

Automata operating on general graphs have been introduced by virtue of graphoids. In this paper we construct a graph automaton that recognizes $k$-colorable graphs.