k-Colorability is Graph Automaton Recognizable
  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. 
Antonios Kalampakas
cs.FL cs.DM