Graph Automata and Graph Colorability


  • Antonios Kalampakas AUM



Graph Colorability, Graph Theory


Automata recognizing graphs can be constructed by employing the algebraic structure of graphoids. For the construction of a graph automaton, the relations over the Kleene star of the state set must constitute a graphoid. Hence different kinds of graphoids produce graph automata with diverse operation and recognition capacity. In this paper we show that graph colorability is recognized by automata operating over the simplest possible abelian graphoid.


How to Cite

Kalampakas, A. (2023). Graph Automata and Graph Colorability. European Journal of Pure and Applied Mathematics, 16(1), 112–120.