EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 1, 2023, 112-120 ISSN 1307-5543 – ejpam.com Published by New York Business Global Graph Automata and Graph Colorability Antonios Kalampakas College of Engineering and Technology, American University of the Middle East, Kuwait Abstract. 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. 2020 Mathematics Subject Classifications: 68R10,68Q45, 68Q70 Key Words and Phrases: Graph Theory, Graph Automata, Graph Colorability 1. Introduction Automata on general (hyper)graphs were constructed for the first time in [5] by uti- lizing the algebraic properties of graphoids, i.e., magmoids satisfying the 15 equations of graphs which are specified in [2]. The notion of magmoids, introduced by Arnold and Dauchet in [1], is the algebraic structure employed to generate graphs from a finite set in a role similar to that of monoids for the generation of strings. A magmoid is a doubly ranked set equipped with two operations which are associative, unitary and mutually coherent in a canonical way (cf. [4] and [6]). In [7] Engelfriet and Vereijken proved that every graph with edges labeled over a finite doubly ranked set Σ can be built from a specific finite set of elementary graphs D, together with the elements of Σ, by using the operations of graph product and graph sum. From this result it is derived that graphs can be organized into a magmoid with operations product and sum. Although, as it was observed in [7], every hypergraph can be constructed in an infinite number of ways, this ambiguity was settled in [2] (see also [3]) by determining a finite set of equations E with the property that two expressions represent the same hypergraph, if and only if, one can be transformed into the other through them. Commencing from this result, a graphoid M is defined as a magmoid with a designated set of elements that satisfy the equations E . Hence GR(Σ) can be structured into a graphoid by virtue of the set D of elementary graphs. The relational magmoid over a set Q is constructed by defining the operations of composition and sum on the set of relations DOI: https://doi.org/10.29020/nybg.ejpam.v16i1.4629 Email addresses: antonios.kalampakas@aum.edu.kw (A. Kalampakas) https://www.ejpam.com 112 © 2023 EJPAM All rights reserved. A. Kalampakas / Eur. J. Pure Appl. Math, 16 (1) (2023), 112-120 113 from Qm to Qn. This set is structured into a relational graphoid over Q, by specifying a set D of relations that satisfy the equations E . A relational graphoid is called abelian when a particular relation of D consists of all the transpositions in Q. In [5] graph automata, with state set Q, were introduced by virtue of a specific abelian relational graphoid, denoted here by TSRel(Q), and by exploiting the fact that GR(Σ) is the free graphoid generated by Σ. In the same paper it is postulated that different kinds of graphoids will produce graph automata with diverse operation and recognition capacity. In [8] it is shown that all abelian relational graphoids are characterized in the following way: a set Q generates an abelian relational graphoid if and only if Q is partitioned into disjoint abelian groups with operations univocally correlated with D. In other words it is proved that organizing Rel(Q) in a relational graphoid is equivalent to partitioning the set Q and structuring every class in a group. The particular graphoid TSRel(Q) employed in [5] corresponds to the partitioning of Q into singleton sets each one being the trivial group. Hence, due to [8], it is the simplest possible abelian relational graphoid. The smallest number of colors needed to color the vertices of the graph so that no two adjacent vertices share the same color is the chromatic number of the graph. A set of graphs is k-colorable if every graph of the set has chromatic number at most k. In this paper we construct for every k, a graph automaton over the abelian graphoid TSRel(Q) which accepts all the k-colorable graphs. Hence it is manifested that graph automata are capable of recognizing important classes of graphs even when operating on the most trivial of the known graphoids. In the following section we recall basic definition for magmoids and hypergraphs. Graphoids are presented in Section 3 and the definition of a graph automaton is given. In Section 4 we construct the graph automaton that recognizes k-colorable graphs and illustrate its operation. Conclusions and future work are discussed in the last section. 2. Magmoids and Hypergraphs A doubly ranked set (Am,n)m,n∈N is a set A together with a function rank : A → N× N we set Am,n = {a ∈ A | rank(a) = (m,n)}. In what follows we will drop the subscript and denote a doubly ranked set simply by A = (Am,n). A magmoid is a doubly ranked set M = (Mm,n) equipped with two operations ◦ : Mm,n ×Mn,k → Mm,k, □ : Mm,n ×Mm′,n′ → Mm+m′,n+n′ , which are associative in the obvious way, satisfy the distributivity law (f ◦ g)□ (f ′ ◦ g′) = (f □ f ′) ◦ (g □ g′) whenever all the above operations are defined and are equipped with a sequence of con- stants en ∈ Mn,n, called units, such that em ◦ f = f = f ◦ en, e0 □ f = f = f □ e0, em □ en = em+n A. Kalampakas / Eur. J. Pure Appl. Math, 16 (1) (2023), 112-120 114 hold for all f ∈ Mm,n and all m,n ∈ N. Notice that, due to the last equation, the elements en are uniquely determined by e1. From now on e1 will be simply denoted by e. The free magmoid mag(Σ) generated by a doubly ranked set Σ is constructed in [2]. The sets Relm,n(Q) of all relations from Qm to Qn Relm,n(Q) = {R | R ⊆ Qm ×Qn} can be structured into a magmoid with ◦ being the usual relation composition and □ defined as follows: for R ∈ Relm,n(Q) and S ∈ Relm′,n′(Q) R□ S = {(u1u2, v1v2) | (u1, v1) ∈ R and (u2, v2) ∈ S)}, where u1 ∈ Qm, u2 ∈ Qm′ , v1 ∈ Qn, v2 ∈ Qn′ . Notice that Q0 = {ε}, where ε is the empty word of Q∗. The units are given by e0 = {(ε, ε)} and e = {(g, g) | g ∈ Q}. We denote by Rel(Q) = (Relm,n(Q)) the magmoid constructed in this way and call it the relational magmoid of Q. An (m,n)-(hyper)graph G = (V,E, s, t, l, begin, end) with edge labels from a doubly ranked set Σ = (Σm,n) is a tuple consisting of the set of nodes or vertices V , the set of edges E, the source and target functions s : E → V + and t : E → V + respectively, the labeling function l : E → Σ such that rank(l(e)) = (|s(e)|, |t(e)|), for all e ∈ E, and the sequences of begin and end nodes begin ∈ V ∗ and end ∈ V ∗ with |begin| = m and |end| = n. Notice that vertices can be duplicated in the begin and end sequences of the graph and also at the sources and targets of the edges. Isomorphism between two graphs is defined in the obvious way and we shall not distinguish between two isomorphic graphs. The set of all (m,n)-graphs over Σ is denoted by GRm,n(Σ) and we set GR(Σ) = (GRm,n(Σ))m,n∈N. Ordinary unlabeled directed graphs are obtained as a special case of hypergraphs i.e., in the case that each hyperedge is binary (has one source and one target), every edge has the same label and the sequences begin and end are the empty word. Given the (m,n)-graph G = (V,E, s, t, l, begin, end) and and the (n, k)-graph H = (V ′, E′, s′, t′, l′, begin′, end′) then their product G ◦H is the (m, k)-graph that is obtained by taking the disjoint union of G and H and then identifying the ith end node of G with the ith begin node of H, for every i ∈ {1, ..., n}; also, begin(G ◦H) = begin(G) and end(G ◦H) = end(H). The sum G□H of arbitrary graphs G andH is their disjoint union with their sequences of begin nodes concatenated and similarly for their end nodes (see [5, 8] for examples). For every n ∈ N we denote by En the discrete graph of rank (n, n) with nodes x1, ..., xn and begin = end = x1 · · ·xn; we write E for E1. It is straightforward to verify that GR(Σ) = (GRm,n(Σ)) with the operations defined above is a magmoid, whose units are the graphs En. A. Kalampakas / Eur. J. Pure Appl. Math, 16 (1) (2023), 112-120 115 3. Graphoids and Graph Automata In this section we present graph automata by employing the algebraic structure of graphoids as introduced in [5]. We denote by Ip,q the discrete (p, q)-graph that has a single node x and whose begin and end sequences are x · · ·x (p times) and x · · ·x (q times) respectively, Π is the discrete (2, 2)-graph that has two nodes x and y and whose begin and end sequences are xy and yx, respectively, also for every σ ∈ Σm,n, we denote again by σ the (m,n)-graph having only one edge and m+ n nodes x1, . . . , xm, y1, . . . , yn. The edge is labeled by σ, and the begin (resp. end sequence) of the graph is the sequence of sources (resp. targets) of the edge, viz. x1 · · ·xm (resp. y1 · · · yn). Engelfriet and Vereijken, in [7], presented an algorithm that inductively constructs every graph G ∈ GR(Σ) from the set Σ ∪ {Π, I01, I21, I10, I12, } by using graph product and graph sum. However, there are infinitely many ways to construct a given graph. This was overridden by identifying a finite set E of equations with the property that two expressions represent the same graph if and only if one can be transformed into the other through these equations [2]. It is evident from this discussion that the equations E are satisfied in GR(Σ). Magmoids with such a property are called graphoids. Formally, a graphoid M = (M,D) consists of a magmoid M and a set D = {s, d01, d21, d10, d12}, with s ∈ M2,2, dκλ ∈ Mκ,λ, such that the following equations hold: s ◦ s = e2 (1) (s□ e) ◦ (e□ s) ◦ (s□ e) = (e□ s) ◦ (s□ e) ◦ (e□ s) (2) (e□ d21) ◦ d21 = (d21 □ e) ◦ d21 (3) (e□ d01) ◦ d21 = e (4) s ◦ d21 = d21 (5) (e□ d01) ◦ s = (d01 □ e) (6) (s□ e) ◦ (e□ s) ◦ (d21 □ e) = (e□ d21) ◦ s (7) A. Kalampakas / Eur. J. Pure Appl. Math, 16 (1) (2023), 112-120 116 d12 ◦ (e□ d12) = d12 ◦ (d12 □ e) (8) d12 ◦ (e□ d10) = e (9) d12 ◦ s = d12 (10) s ◦ (e□ d10) = (d10 □ e) (11) (d12 □ e) ◦ (e□ s) ◦ (s□ e) = s ◦ (e□ d12) (12) d12 ◦ d21 = e (13) (d12 □ e) ◦ (e□ d21) = d21 ◦ d12 (14) sm,1 ◦ (p□ e) = (e□ p) ◦ sn,1, for all p ∈ Mm,n (15) where sm,1 is defined inductively by s and represents the graph associated with the per- mutation that interchanges the last n numbers with the first one [2]. We point out that the set of Equations (15) it only has to be valid for the elements of Σ in order to hold for every element of a magmoid generated by Σ [2]. Thus the pair GR(Σ) = (GR(Σ), D), with D = {Π, I01, I21, I10, I12} is a graphoid and in fact it is the free graphoid generated by Σ as it is illustrated in [5]. Given graphoids (M,D) and (M ′, D′), a magmoid morphism H : M → M ′ preserving D-sets, i.e., H(s) = s′ and H(dκλ) = d′κλ, is called a morphism of graphoids. Graphoids constructed from the magmoid of relations Rel(Q) over a given set Q are called relational graphoids and a relational graphoid is called abelian when s = {(g1g2, g2g1) | g1, g2 ∈ Q}. The abelian relational graphoid TSRel(Q) = (Rel(Q), D) that was used for the introduc- tion of graph automata is constructed by setting s as above and d01 = {(ε, g) | g ∈ Q}, d21 = {(gg, g) | g ∈ Q}, d10 = {(g, ε) | g ∈ Q}, d12 = {(g, gg) | g ∈ Q}. A nondeterministic relational graph automaton is a structure A = (Σ, Q,Rel(Q), δ, I, T ), A. Kalampakas / Eur. J. Pure Appl. Math, 16 (1) (2023), 112-120 117 where Σ is the doubly ranked set of hyperedge labels, Q is the finite set of states, Rel(Q) is a relational graphoid over Q, δ : Σ → Rel(Q) is the doubly ranked transition function and I, T are initial and final rational subsets of Q∗. The function δ is uniquely extended into a morphism of graphoids δ̄ : GR(Σ) → Rel(Q), where δ̄(Iκλ) = dκλ and δ̄(Π) = s, and the behavior of A is given by |A| = {F | F ∈ GRm,n(Σ), δ̄A(F ) ∩ (I (m) A × T (n) A ) ̸= ∅, m, n ∈ N} where I (m) A = IA ∩Qm and T (n) A = TA ∩Qn. From their construction, graph automata are finite machines due to the fact that the set of equations (1)-(15) is finite. A graph language is called recognizable whenever it is obtained as the behavior of a graph automaton. The class of all such languages over the doubly ranked set Σ is denoted by Rec(Σ). 4. A Graph Automaton Recognizing k-colorable Graphs In this section we construct a relational graph automaton over the abelian graphoid TSRel(Q) recognizing k-colorable graphs. For k ∈ N∗, we set Ak clr = (Σ, Q,TSRel(Q), δ, I, T ) with • Σ = {a}, rank(a) = (1, 1), • Q = {1, 2, . . . , k}, • δ(a) = {(i, j) | i, j ∈ Q, i ̸= j}, • I = T = {ε}. It is clear that the automaton Ak clr reads unlabeled (0, 0)-graphs with binary edges (one source and one target per edge), i.e., ordinary directed graphs. As an example we shall illustrate the operations of A2 clr,A3 clr and A4 clr on the following graphs, where the label in every edge is a and thus omitted. G F K3,3 One of the representations of G is G = I01 a I12 ( a a )( a E ) I21 I10 A. Kalampakas / Eur. J. Pure Appl. Math, 16 (1) (2023), 112-120 118 where graph product and graph sum are denoted, for simplicity, by horizontal and vertical concatenation. Note that since GR(Σ) is the free graphoid, the operation of the automaton is the same for every representation of G. The consumption of G by A3 clr gives δ̄(G) = d01 δ(a) d12 ( δ(a) δ(a) )( δ(a) e ) d21 d10 and an accepting sequence of transitions is {ε}d01{1}δ(a){2}d12 { 2 2 }( δ(a) δ(a) ){ 3 1 }( δ(a) e ){ 1 1 } d21{1} d10{ε} where the states are indicated in brackets. In graphical representation the states that the automaton reaches at each state are 1 2 3 1 which is actually a proper 3-coloring of G. Similarly, a representation for F is F = I01 I13 a a a   E I12 E   E a a E ( I21 I21 )( a E ) I21 I10 and it is clear that there exists no successful transition of F by A3 clr. A successful transition of F by A4 clr is {ε}d01{1}d13  1 1 1  δ(a) δ(a) δ(a)  2 3 4   e d12 e   2 3 3 4   e δ(a) δ(a) e   2 2 4 4 ( d21 d21 ){ 2 4 }( δ(a) e ){ 4 4 } d21{4} d10{ε} and the corresponding 4-coloring that is obtained by the state distribution of this transition is 1 3 2 4 A. Kalampakas / Eur. J. Pure Appl. Math, 16 (1) (2023), 112-120 119 Note that the elementary graph Π is not necessary for the representation of G and F . More generally, all planar graphs can be represented without employing Π. On the other hand, the non-planar graph K3,3 is expressed as K3,3 = I01 I01 I01 I13 I13 I13  a ... a Πs I31 I31 I31 I10 I10 I10  where in the third parenthesis there are 9 a and Πs stands for the graph that is associated with the permutation ( 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 ) Notice that as it is shown in [2] for every permutation we can construct, inductively by Π and E a graph that represents it. The graphK3,3 is 2-colorable and an accepting transition of A2 clr is {ε} d01 d01 d01  1 1 1  d13 d13 d13   1 ... 1  δ(a) ... δ(a)   2 ... 2  ds  2 ... 2  d31 d31 d31  2 2 2  d10 d10 d10  {ε} Hence, if we denote by kCol the set of all k-colorable graphs, we obtain Theorem 1. For every k ∈ N, the graph language kCol is recognizable. 5. Discussion We showed that k-colorability is graph automaton recognizable even when the automa- ton operates over the most trivial abelian relational graphoid. This indicates that the graph automaton is a robust recognition mechanism and evokes numerous issues regard- ing the class of automaton recognizable graph languages. The introduced graph automata are nondeterministic in the sense that if σ ∈ Σm,n then δ(σ) is a relation in Qm × Qn. The deterministic version of this definition is obtained by requiring that δ(σ) is a function from Qm to Qn, i.e., δ(σ) is an element of Funct(Q) which is a submagmoid of Rel(Q) called the magmoid of functions [5]. It is interesting to compare the two classes and in particular to investigate the existence of a deterministic graph automaton recognizing k-colorable graphs. As it has been proved in [8] an infinite number of non-isomorphic abelian relational graphoids exists. Two questions that naturally arise concern the recog- nition capacity of the corresponding automata as well as the existence of non-abelian or non-relational graphoids. Moreover, the time complexity for checking if a specific graph belongs to the behavior of a graph automaton grows polynomially as a function of the number of states |Q| (see [5]). On the other hand, the complexity of the membership problem for a given graph automaton as a function of the size of the graph for both the deterministic and the nondeterministic REFERENCES 120 case has not been investigated. Such a result would classify automaton recognizable graph languages according to their computational complexity. In a different approach, graph colorability can be investigated for directed fuzzy graphs, introduced in [9, 10] in relation with the existing concept of fuzzy graph coloring as in [11]. Additionally, graph recognizability via automata could also be applied in scheduling problems using vertex colorability as in [12]. References [1] A Arnold and M Dauchet. Théorie des magmoides. RAIRO Theoret. Inform. Appl., 12:235–257, 1978. [2] S Bozapalidis and A Kalampakas. An axiomatization of graphs. Acta Inform., 41:19– 61, 2004. [3] S Bozapalidis and A Kalampakas. Automata on patterns and graphs. In Proceedings of the 1st Conference on Algebraic Informatics, pages 31–52, 2006. [4] S Bozapalidis and A Kalampakas. Recognizability of graph and pattern languages. Acta Inform., 42:553–581, 2006. [5] S Bozapalidis and A Kalampakas. Graph automata. Theoret. Comput. Sci., 393:147– 165, 2008. [6] S Bozapalidis and A Kalampakas. Pattern language recognition and generation. Pure Mathematics and Applications, 22:1–38, 2011. [7] J Engelfriet and J Vereijken. Context-free graph grammars and concatenation of graphs. Acta Informatica, 34:773–803, 1997. [8] A Kalampakas. Graph automata: The algebraic properties of abelian relational graphoids. Lecture Notes in Computer Science, 7020:168–182, 2011. [9] A Kalampakas, S. Spartalis, and L. Iliadis. Syntactic recognizability of graphs with fuzzy attributes. Fuzzy Sets and Systems, 229:91–100, 2013. Theme: Computer Science. [10] A Kalampakas, S Spartalis, L Iliadis, and E Pimenidis. Fuzzy graphs: algebraic structure and syntactic recognition. Artif. Intell. Rev., 42:479–490, 2014. [11] S. Munoz, M. T. Ortuno, J. Ramirez, and J. Yanez. Coloring fuzzy graphs. Omega, 33(3):211–221, 2005. [12] U Ufuktepe and G Bacak. Applying mathematica and webmathematica to graph coloring. Future Generation Computer Systems, 23(5):716–720, 2007.