Autotopism stabilized colouring games on rook's graphs

Autotopism stabilized colouring games on rook’s graphs Raúl M. Falcón a,∗, Stephan Dominique Andresb aDepartment of Applied Mathematics I, University of Seville, Spain bFaculty of Mathematics and Computer Science, FernUniversität in Hagen, Germany a r t i c l e i n f o Article history: Received 30 September 2017 Received in revised form 3 May 2019 Accepted 9 May 2019 Available online 31 May 2019 Keywords: Graph colouring game Partial Latin square Autotopism a b s t r a c t This paper deals with the Θ-stabilized colouring game on the n×nrook’s graph, which constitutes a variant of the classical colouring game on finite graphs so that each configuration of the game is uniquely related to a partial Latin square of order nthat respects a given autotopism Θ. The complexity of this variant is examined by means of its Θ-stabilized game chromatic number, whose currently known upper bound is improved to 2n−1. Particularly, we introduce the concept of a passing board that enables us to describe a constructive method to compute this number. Based on this method, we explicitly determine the game chromatic number associated to those n×nrook’s graphs, for which n≤4. 1. Introduction Based on the graph colouring problem, the colouring game [5,19] is played on a finite graph Gby two players, Alice (A) and Bob (B), with Alice playing first. During the game, they must alternately colour exactly one uncoloured vertex of the graph with a colour taken from a given palette so that no two adjacent vertices are coloured with the same colour. Alice wins if all the vertices are coloured at the end of the game; otherwise, Bob wins. The game chromatic number χg(G) is the smallest integer ksuch that Alice has a winning strategy in case of playing with a palette of kcolours. Such a number always exists, being not greater than the number of vertices of the graph. In the literature, many efforts have been done to reduce the upper bound for the game chromatic number of planar graphs [4,22,33]. Further, as the game may change significantly when Bob begins instead of Alice, different authors [1,2,32] have distinguished between the game chromatic numbers χgA(G) and χgB(G) depending on whether Alice or Bob begins the game, which is in turn denoted as gAor gB, respectively. In 2011, Schlund [27] introduced the game chromatic number of a Latin square of order nas that one related to the n×nrook’s graph, for which he established some lower and upper bounds. Every position that occurs during a colouring game played on such a graph by means of a given palette of ncolours corresponds to a partial Latin square of order n. Based on this fact and motivated by the current growing research on applications of autotopisms of Latin squares and their related structures in different directions as graph theory [8,18,31], enumerative combinatorics [6,16,20,23,24], algebraic combinatorics [7,21,25,28] or cryptography [12,13,29], amongst others, the authors [3] have recently generalized the colouring game proposed by Schlund by introducing the Θ-stabilized colouring game on the n×nrook’s graph so that each position of the game corresponds to a partial Latin square having Θas an autotopism. Based on the known distribution of cycle structures of autotopisms of partial Latin squares [14,15,17,30], this paper provides an in-depth analysis on the computation of the game chromatic number of such a colouring game. ∗Corresponding author. E-mail addresses: [email protected] (R.M. Falcón), [email protected] (S.D. Andres). https://doi.org/10.1016/j.dam.2019.05.006 0166-218X/ 201 Fig. 1. Identification of a partial Latin square with a partial colouring of a rook’s graph. The paper is organized as follows. Section 2deals with some preliminary concepts and results on partial Latin squares and the Θ-stabilized colouring game that are used throughout the paper. Particularly, we describe both conditions of feasibility and extendability that must satisfy the autotopism Θin order to get a well-defined colouring game. After that, in Section 3, in order to illustrate the constructive proofs that are shown throughout the paper, we introduce the concepts of passing boards and Θ-symmetric partial Latin squares. Finally, in Section 4we determine the Θ-stabilized game chromatic numbers for every extendable isotopism Θ∈Inwith n≤4. 2. Preliminaries This section deals with some basic results on partial Latin squares and the Θ-stabilized colouring game that are used throughout the paper. For more details about both topics, we refer the reader to [11] and [3], respectively. 2.1. Partial Latin squares Apartial Latin square of order nis an n×narray in which each cell is either empty or contains one symbol chosen from a set of nelements so that each symbol occurs at most once in each row and in each column. It is a Latin square if every cell is non-empty. Hereafter, we denote as PLSnthe set of partial Latin squares of order n, with symbols chosen from the set [n] := {1, . . . , n}. Thus, for instance, the following three arrays are partial Latin squares in the set PLS3. P≡ 2 1 1 3 Q≡ 2 1 1 2 3 R≡ 1 3 2 3 (1) Every partial Latin square P∈PLSnis uniquely related to a partial colouring of a labelled n×n rook’s graph, that is, of a Cartesian product Kn□Knof complete graphs. From here on, we denote such a graph as Rn. More specifically, each cell of P is identified, by means of a label, with a vertex of the graph so that two vertices are adjacent if and only if their associated cells are in the same row or in the same column of the array. In turn, each vertex of the graph is coloured according to the symbol appearing in the corresponding cell of P. Colouring an uncoloured vertex in a rook’s graph is, therefore, equivalent to filling an empty cell in a partial Latin square with a symbol. Fig. 1 shows, for instance, the partial 3-colouring of the rook’s graph related to the partial Latin square Pin (1). We have used the style ◦to represent uncoloured vertices and the styles ▲,▼and ♦to represent, respectively, those coloured vertices related to the symbols 1, 2 and 3. An entry of a partial Latin square P∈PLSnis any triple (i,j,pij)∈ [n]×[n]×[n]that is uniquely related to a non-empty cell of Pwhich is situated in the ith row and jth column, and contains the symbol pij. The partial Latin square Pis uniquely determined by the set of all its entries, which is denoted as E(P). If this set is empty, then the partial Latin square Pis called trivial. Further, it is said that Pis contained in a partial Latin square Q∈PLSnif E(P)⊆E(Q). Thus, for instance, the partial Latin square P∈PLS3in (1) has {(1,1,2),(1,2,1),(2,1,1),(3,3,3)}as set of entries. This is contained in the partial Latin square Qof the same figure, which also contains the entry (2,2,2). Let Snand Inrespectively denote the symmetric group on nelements and the Cartesian product Sn×Sn×Sn. An isotopism of PLSnis any triple Θ=(α, β, γ )∈In, where α,βand γconstitute, respectively, a permutation of the rows, columns and symbols of any partial Latin square P∈PLSn. This gives rise to the isotopic partial Latin square PΘ∈PLSn, whose set of entries is E(PΘ)= {(α(i), β(j), γ (k)) |(i,j,k)∈E(P)}. If γcoincides with the trivial permutation Id, then the isotopism Θis called principal. If PΘ=P, then the isotopism Θis said to be an autotopism of the partial Latin square P. Necessary conditions for isotopisms of partial Latin squares to be an autotopism are exposed in [14,15,23,26,30]. The set of autotopisms of Pis endowed of group structure with the componentwise composition of permutations. The set of non-trivial partial Latin squares having a given isotopism Θ∈Inin their autotopism group is denoted as PLSΘ. Thus, for instance, the triple ((123),(12)(3),(13)(2)) ∈I3is an isotopism between the partial Latin squares Pand Rin (1), whereas the partial Latin square Qin the same figure is contained in the set PLS((12)(3),(12)(3),Id). The cardinality of each set PLSΘonly depends on the cycle structure of the isotopism Θ. Recall that the cycle structure of a permutation π∈Snis the expression zπ:= nλπ n. . . 1λπ 1, where λπ ldenotes the number of cycles of length lin the 202 unique decomposition of πas a product of disjoint cycles. In practice, only those factors for which λπ l>0 are written, and any factor of the form l1is replaced by l. Thus, for instance, the cycle structure of the permutation (123)(45)(67) ∈S7 is 322. Two permutations π1and π2in Snhave the same cycle structure if and only if they are conjugate, that is, there exists a third permutation π3∈Snsuch that π2=π3π1π−1 3. As a natural generalization, the cycle structure of an isotopism Θ=(α, β, γ )∈Inis defined as the triple zΘ:= (zα,zβ,zγ). Two isotopisms have the same cycle structure if and only if they are conjugate. The set of all cycle structures of Latin squares of order n≤17 is available in [30] (see also [14]). In order to deal with the set of all cycle structures of partial Latin squares, we define the set LCM := {(a,b,c)∈N3|lcm(a,b)=lcm(a,c)=lcm(b,c)=lcm(a,b,c)}, where lcm denotes the least common multiple. Thus, for instance, the triple of positive integers (2,3,6) belongs to the set LCM. In particular, an isotopism Θ=(α, β, γ )∈Inis an autotopism of a non-trivial partial Latin square if and only if there exists a triple (a,b,c)∈LCM such that λα aλβ bλγ c>0. Thus, for example, the principal isotopism ((12)(3),(12)(3),Id) ∈I3 is an autotopism, because its cycle structure is (21,21,13) and we have, for instance, that (2,2,1) ∈LCM. Nevertheless, the isotopism ((123),(12)(3),(13)(2)) ∈I3is the autotopism of none partial Latin square of order 3, because its cycle structure is (3,21,21) and none of the triples (3,2,2), (3,2,1), (3,1,2) and (3,1,1) belongs to the set LCM. We conclude this subsection by remarking how any isotopism in Indetermines a unique partition of the set [n] × [n], which constitutes in turn the set of cells of any partial Latin square of order n. In order to see it, for a positive integer i≤n, let ℓπ(i) denote the length of the cycle Cin the unique decomposition of a permutation π∈Sninto disjoint cycles such that π(i)=C(i). Thus, for instance, ℓ(12)(3)(1) =2. Then, the cell orbit of a pair (i,j)∈ [n] × [n]under the action of an isotopism Θ=(α, β, γ )∈Inis defined as the set oΘ((i,j)) := {(αm(i), βm(j)) |m∈ {0, . . . , lcm(ℓα(i), ℓβ(j)) −1}}. The cell orbit is symbol-free in a given partial Latin square P∈PLSnif all its elements correspond to empty cells in P. Otherwise, it is marked. It is complete if all its elements correspond to non-empty cells in P. Particularly, P∈PLSΘif and only if (a) every cell orbit is complete or symbol-free in P, and (b) if (i,j,k)∈E(P), then the cell orbit of (i,j) is complete and formed by the entries (αm(i), βm(j), γ m(k)), for all positive integers m≤lcm(ℓα(i), ℓβ(j)). For instance, the partition of the set [3] × [3]under the action of the principal isotopism Θ=((12)(3),(12)(3),Id) ∈I3is the set formed by the five cell orbits o1= {(1,1),(2,2)},o2= {(1,2),(2,1)},o3= {(1,3),(2,3)},o4= {(3,1),(3,2)}and o5= {(3,3)}(see (2), where the cells related to each orbit have been respectively filled by the symbols ▲,▼,♦,△and ▽). Observe that, in the partial Latin square P∈PLS3in (1), the cell orbits o2and o5are complete, and the cell orbits o3and o4are empty. Nevertheless, P∈ PLSΘ, because even if the cell orbit o1is marked, this is not complete. ▲ ▼ ♦ ▼ ▲ ♦ △△▽ (2) 2.2. The Θ-stabilized colouring game In this subsection we describe the Θ-stabilized colouring game, which is the aim of our study. Let us start by exposing the two conditions that any isotopism Θ=(α, β, γ )∈Inmust satisfy in order to get a well-defined colouring game. First, the isotopism Θis said to be feasible if every three positive integers a,b,c∈ [n]satisfying that λα a·λβ b·λγ c>0 must involve that (a,b,c)∈LCM. Thus, for instance, the isotopism ((12)(34)(56),(123)(456),(123456)) ∈I6is feasible because its cycle structure is (23,32,6) and (2,3,6) ∈LCM. Nevertheless, the principal isotopism ((12)(3),(123),Id) ∈I3 is not feasible because its cycle structure is (21,3,13) and, for example, lcm(2,3) = lcm(2,1). Second, the isotopism Θis said to be extendable if the isotopism Θ′=(α, β, γ ′)∈In′is feasible, for all n′>nand γ′∈Sn′such that γ′(k)=γ(k) if k≤n, and γ′(k)=k, otherwise. The isotopism Θ′is called anatural extension of size n′of Θ. It is feasible only if Θis also feasible and all the cycles in the unique decompositions of both permutations αand βinto a product of disjoint cycles have the same length. Thus, for instance, the feasible isotopism ((12)(34)(56),(123)(456),(123456)) ∈I6is not extendable. On the other hand, the isotopism ((12)(34),(12)(34),(12)(3)(4)) ∈I4is extendable, because it is feasible and all the cycles of the permutations of rows and columns have the same length two. The Θ-stabilized colouring game is, therefore, played by two players, Alice and Bob, on the rook’s graph Rnwith regard to an extendable isotopism Θ∈Inand a given palette of n′≥ncolours. As in the conventional colouring game, Alice wins if all the vertices of the graph are coloured at the end of the game; otherwise, Bob wins. At the beginning of the game, none of the vertices of the rook’s graph are coloured, that is, as a board we consider the trivial partial Latin square of order n. Alternately, the players choose an empty cell (i,j)∈ [n] × [n]in the board and a symbol k∈ [n′], and colour the former by the latter by setting (i,j,k)∈E(P). The resulting array is said to be a configuration of the colouring game and has to obey the following three rules. 203 •Rule (1) It must be a partial Latin square. •Rule (2) It must be Θ-compatible, that is, the new entry (i,j,k)∈E(P) satisfies that, for each positive integer m≤lcm(ℓα(i), ℓβ(j)), either the cell (αm(i), βm(j)) is empty in P, or (αm(i), βm(j), γ m(k)) ∈E(P). •Rule (3) For each positive integer m<lcm(ℓα(i), ℓβ(j)), there does not exist an entry of the form (αm(i),j′, γ m(k)) or (i′, βm(j), γ m(k)) in the set E(P), where j′= βm(j) and i′= αm(i). Example 1. In order to illustrate the different rules that we have been just exposed, in (3) we show three forbidden configurations for a ((12)(34),(12)(34),(12)(3)(4))-stabilized colouring game. Below each configuration, we indicate the rule that forbids each configuration. We also indicate with a star those cells that are involved in the infringement of the rule. 2∗3 2∗ 3 1 4 3 1 3 4 2∗3 3 2∗ 4 3 1 3 4 2∗3 3∗ 1∗4 3 3 4 Rule 1 Rule 2 Rule 3 (3) Thus, Rule 1 is violated by the first array, because both cells (1,1) and (1,4) contain the same symbol 2. Further, according to Rule 2, the existence of the entry (1,1,2) in the three arrays implies that the cell (2,2) should either be empty or contain the symbol 1. Hence, Rule 2 is infringed by the second array, because the cell (2,2) is not empty and contains the symbol 2. Finally, Rule 3 is violated by the third array, because, even if the cell (2,2) is empty, the symbol 1 already appears in the second column. Concerning the condition of Θ-compatibility, let us remark that the set PLSΘis not empty if and only if there exists a Θ-compatible partial Latin square for which every marked orbit is complete. Thus, for instance, both partial Latin squares Pand Qin (1) are ((12)(3),(12)(3),Id)-compatible, but only every marked orbit in Qis complete. As a consequence, the principal isotopism ((12)(3),(12)(3),Id) is an autotopism of Q. The three rules of the Θ-stabilized colouring game enable us to ensure that Alice always wins when a player colours any cell of the last symbol-free cell orbit of the board. Moreover, if there exists at least one symbol-free cell orbit, then (a) any empty cell can be coloured, and (b) if a colour k>nof a natural extension of Θdoes not appear in any cell, then there exists at least one empty cell that can be coloured with that colour. That is, the Θ-stabilized colouring game is well-defined. The smallest size n′>nof a natural extension of the isotopism Θfor which Alice has a winning strategy is called the Θ-stabilized game chromatic number and is denoted χΘ gA. Similarly to the classical colouring game, we distinguish the variant χΘ gBin case Bob starts the game. If Θis the trivial isotopism, then these values correspond to the usual game chromatic numbers χgA(Rn) and χgB(Rn). In general, both values only depend on the cycle structure of the isotopism Θ and we have n≤χΘ g≤ |o(Θ)| + n−1 (4) for all g∈ {gA,gB}, where |o(Θ)|denotes the number of different cell orbits in which the set [n] × [n]is partitioned by Θ. Theorem 2 ([3]).The following results hold. (a) χgA(R1)=1=χgB(R1). (b) χgA(R2)=3>2=χgB(R2). (c) χgA(R3)=3<4=χgB(R3). (d) Let Θ∈Inbe an extendable principal isotopism with cycle structure (n,n,1n). Then, χΘ gA=n=χΘ gB. 3. Θ-symmetric passing boards Let Θ∈Inbe an extendable isotopism. During the development of any Θ-stabilized colouring game, whenever a player colours a cell within an empty cell orbit, we obtain a configuration for which the colouring of the rest of the empty cells in the orbit is uniquely determined by Rule 2. Colouring one of these cells in a later move is considered, therefore, as a passing move. Based on this, we name these cells as passing cells. Besides, we define the passing board of a given configuration as the array that results after colouring in black the background of all its passing cells and writing in each one of them the symbol that it would contain. Thus, for instance, the passing board that results after the first player 204 of a ((1234), (1234), (1234))-stabilized colouring game colours the cell (1, 1) with the colour 1 is 1 2 3 4 (5) In order to describe an equivalence relation among passing boards, we introduce the concept of being Θ-isotopic. To this end, given a permutation π∈Snand a positive integer i≤n, let us define the set Cπ(i):= {πm(i)|m≤n}, which constitutes indeed the orbit of iunder the action of π. According to the notation used in Section 2, the cardinality of this set is ℓπ(i). Then, given an extendable isotopism Θ=(α, β, γ )∈In, we define the Θ-block associated to a pair (i,j)∈ [n]×[n]as the set BΘ(i,j):= {(i′,j′)∈ [n]×[n] | i′∈Cα(i),j′∈Cβ(j)}.(6) We say that two pairs (i,j) and (i′,j′) in the set [n]×[n]are Θ-related if BΘ(i,j)=BΘ(i′,j′), that is, if they belong to the same Θ-block. This constitutes an equivalence relation, because of the uniqueness of the decomposition of both permutations αand βinto disjoint cycles. More specifically, since the isotopism Θis extendable, all these cycles have the same length and hence, the set of Θ-blocks gives rise to a partition of the set of cells of any partial Latin square of order ninto square arrays. Such a partition is indeed a particular case of the so-called block diagram, which was introduced by Stones et al. [30] in case of dealing with automorphisms of Latin squares. Thus, for instance, the extendable principal isotopism Θ=((12)(34),(12)(34),Id) ∈I4determines four Θ-blocks in the set of cells of any partial Latin square of order 4, which are identified in the following array by the labels B1to B4. B1B1B2B2 B1B1B2B2 B3B3B4B4 B3B3B4B4 (7) We say that two partial Latin squares P,Q∈PLSnare Θ-isotopic if there exists an isotopism Θ′=(α′, β′, γ ′)∈In that preserves the Θ-relation among cells. That is, if two entries (i1,j1,k1) and (i2,j2,k2) in E(P) are Θ-related, then the entries (α′(i1), β′(j1), γ ′(k1)) and (α′(i2), β′(j2), γ ′(k2)) in E(Q) are also Θ-related. Thus, for instance, the following two partial Latin squares are ((12)(34),(12)(34),Id)-isotopic by means of the isotopism ((12)(34),(1)(2)(34),(13)(24)) ∈I4. 1 2 2 4 3 4 3 4 1 2 (8) We say that two partial Latin squares P,Q∈PLSnare Θ-symmetric if Pis Θ-isotopic to Qor to its transpose Qt. Further, we say that two passing boards are Θ-symmetric if their respective underlying partial Latin squares that result from considering both sets of non-empty and passing cells as their sets of entries (that is, in practice, from colouring in white the black background of all the passing cells) are Θ-symmetric. Thus, for instance, the following five passing boards are pairwise non-((12)(34),(12)(34),(12)(34))-symmetric. 1 3 4 2 1 2 1 2 1 2 3 4 1 2 2 1 1 3 2 4 (9) To be Θ-symmetric constitutes an equivalence relation among passing boards that plays an important role in our study. In this regard, the following result holds. Lemma 3. Let Θ∈Inbe an extendable isotopism. If Alice has a winning strategy from a given passing board, then she can establish a similar winning strategy from any other passing board that belongs to the same Θ-symmetric class of the former. The situation is the same for Bob. Proof. The new strategy follows immediately from cloning the original one by means of the isotopism that relates both passing boards. □ As a consequence, the winning strategy that Alice should follow in the development of a Θ-stabilized colouring game can be explicitly determined after an exhaustive study of each one of the Θ-symmetric classes of those passing boards that can result after each possible move. In this regard, when we indicate in the different proofs of the next section that a specific move can be supposed ‘‘without loss of generality’’ (w.l.o.g.), we mean that any other move would give rise to a passing board that is Θ-symmetric to the exposed one. 205 Table 1 Θ-stabilized game chromatic numbers according to cycle structure of Θ. n Cycle structure χΘ gAχΘ gBResult 1 (1,1,1) 1 1 Theorem 2(a) 2 (2,2,2) 3 3 Theorem 6(a) (2,2,12) 2 2 Theorem 2(d) (12,12,12) 3 2 Theorem 2(b) 3 (3,3,3) 3 3 Theorem 6(b) (3,3,13) 3 3 Theorem 2(d) (13,13,13) 3 4 Theorem 2(c) 4 (4,4,4) 5 5 Theorem 6(c) (4,4,22) 6 4 Theorem 6(d) (4,4,212) 5 4 Theorem 6(e) (4,4,14) 4 4 Theorem 2(d) (22,22,22) 5 4 Theorem 6(f) (22,22,14) 5 4 Theorem 6(g) (14,14,14) 6 5 Theorem 6(h) 4. Θ-stabilized game chromatic numbers This section deals with the computation of Θ-stabilized game chromatic numbers for those extendable isotopisms Θ∈In, with n≤4. As we have already pointed out in Section 2, these numbers only depend on the cycle structure of the isotopism. Table 1 gathers all these values for both variants of the game, gAand gB. We also indicate the result in the paper where each game chromatic number is obtained. Let us start our study by improving the upper bound exposed in (4). Lemma 4. Let Θ∈Inbe an extendable isotopism. The number of cell orbits within any partial Latin square having an extendable isotopism Θ∈Inas an autotopism is at least n. Proof. As it has been exposed in the previous section, the extendability of the isotopism Θinvolves that all the Θ-blocks associated to the cells of any partial Latin square in PLSΘare square arrays. Hence, the number of cell orbits within any such an array coincides with its order. The least number of cell orbits associated to an extendable isotopism occurs when the cycle structure of both permutations of rows and columns is n. In such a case, the isotopism gives rise to a unique n×nΘ-block, and thus, to ndifferent cell orbits. □ Proposition 5. Let Θ∈Inbe an extendable isotopism. Then, χΘ g≤2n−1, for all g ∈ {gA,gB}. This improves the upper bound in (4). Proof. The worst situation that can exist to colour an empty cell within a given passing board associated to a Θ-stabilized colouring game is that all its 2n−2 collinear cells (n−1 per row and n−1 per column) are either already coloured or they are passing cells, so that all their associated symbols are pairwise distinct. In such a case, a (2n−1)th colour is required. The square structure of every Θ-block within our passing board involves this number of colours to be enough for Alice to have a winning strategy. The last assertion follows then straightforwardly from Lemma 4.□ Theorem 6. Let Θ∈Inbe an extendable isotopism. Then, (a) If zΘ=(2,2,2), then χΘ gA=3=χΘ gB. (b) If zΘ=(3,3,3), then χΘ gA=3=χΘ gB. (c) If zΘ=(4,4,4), then χΘ gA=5=χΘ gB. (d) If zΘ=(4,4,22), then χΘ gA=6>4=χΘ gB. (e) If zΘ=(4,4,212), then χΘ gA=5>4=χΘ gB. (f) If zΘ=(22,22,22), then χΘ gA=5>4=χΘ gB. (g) If zΘ=(22,22,14), then χΘ gA=5>4=χΘ gB. (h) If zΘ=(14,14,14), then χΘ gA=6>5=χΘ gB. Proof. Since the Θ-stabilized game chromatic number only depends on the cycle structure of the isotopism Θ, we study each assertion separately by focusing on a specific isotopism having the corresponding cycle structure. Whenever it is possible, we indicate optimal moves for each player, which give rise to new configurations that force the next move of the other player. Remark in this regard that colouring a passing cell is never an optimal move, because it does not give any new restriction on the possible colours that can be used in the rest of uncoloured cells. Further, whoever the first 206 player is and except for assertion (e), we suppose, w.l.o.g., that the first move of every game consists of colouring the cell (1,1) with the colour 1. (a) In this case, we have Θ=((12),(12),(12)) ∈I2. This isotopism partitions the set [2] × [2]into two cell orbits: {(1,1),(2,2)}and {(1,2),(2,1)}. Hence, from (4), we have that 2 ≤χΘ g≤3, for all g∈ {gA,gB}. However, it is straightforwardly verified that none Latin square of order 2 has Θas an autotopism and hence, χΘ gA=3=χΘ gB. (b) Suppose Θ=((123),(123),(123)) ∈I3. Whoever the first player is, the resulting passing board after the first move is 1 2 3 .(10) The colouring of the rest of the empty cells is then uniquely determined by Rule 3. (c) Suppose Θ=((1234),(1234),(1234)) ∈I4. If the game is played with four colours, then, whoever the first player is, the second player w.l.o.g. colours either the cell (1,2) with colour 3 or 4 or the cell (1,3) with colour 2 or 4. The resulting passing boards are 1 3 2 4 3 1 2 4 and 1 4 2 1 3 2 3 4 and 1 2 2 3 4 3 1 4 and 1 4 2 1 2 3 3 4 .(11) As a consequence, from Rules 1 and 3, in the first case both cells (1,3) and (1,4) could be coloured only with the symbol 2, which would contradict Rule 1. By symmetry, in the second case, the cells (2,1) and (3,1) could be coloured only with the symbol 4. In the last two cases, one of the cell orbits is not colourable. Hence, any winning strategy for Alice would require a fifth colour. Alice has the following strategy to win with five colours. If Bob begins, she creates the first passing board above with her first move. Whatever Bob’s second move is, the fourth cell orbit is uniquely determined. If Alice begins and Bob creates one of the first two passing boards, then she wins by the same argument. If he creates the third or fourth passing board, then Alice must colour a cell in the cell orbit that can only be coloured with colour 5, and by such a move she wins. If Bob performs a passing move at some time, then just the roles of Alice or Bob beginning are switched. (d) Suppose Θ=((1234),(1234),(12)(34)) ∈I4. If it is Alice who starts the game, then Bob would colour the cell (1,3) with the colour 3. The resulting passing board would be 1 3 2 4 3 1 4 2 .(12) From Rules 1 and 3, the colouring of both cells (1,2) and (1,4) would require two new colours of a natural extension of Θ. Further, if it is Bob who starts the game, then Alice would colour the cell (1,3) with the colour 2. The resulting passing board would be 1 2 2 1 2 1 1 2 .(13) Starting from this passing board and using the four initial colours, any legal colouring of a cell within an empty cell orbit would force the colouring of the rest of the cells. (e) Suppose Θ=((1234),(1234),(12)(3)(4)) ∈I4. In this case, whoever the first player is, we can suppose, w.l.o.g., that the first move of the game consists of colouring the cell (1,1) either with the colour 1 or with the colour 3. If it is Alice who starts the game, then Bob would colour the cell (1,3) with the colour 3 or 1, respectively. The corresponding passing boards would be, respectively, 1 3 2 3 3 1 3 2 and 3 1 3 2 1 3 2 3 .(14) In both cases, a fifth colour is necessary and enough for Alice in order to have a winning strategy. On the other hand, if it is Bob who starts the game by colouring the cell (1,1) with one of the colours 1 or 3, then Alice would colour the cell (1,3) with the colour 2 or 4, respectively. The former would give rise to the passing board (13), 207 whereas the latter would give rise to the passing board 3 4 3 4 4 3 4 3 .(15) In both cases, the four initial colours are enough to colour the rest of the cells. (f) Suppose Θ=((12)(34),(12)(34),(12)(34)) ∈I4. If it is Bob who starts the game, then, in her corresponding moves, Alice always has to colour a cell of the empty cell orbit of the Θ-block associated with the cell that Bob has just coloured. By following this strategy, Alice wins the game with only four colours. On the other hand, if it is Alice who starts the game, then Bob’s first move would give rise to a passing board related to exactly one of the five non-Θ-symmetric classes that are shown in (9). Let us study each case separately. i. In case of dealing with the first passing board in (9), Alice’s next move gives rise to one of the following two non-Θ-symmetric passing boards 1 3 2 4 2 1 and 1 3 4 2 1 2 .(16) In both cases, Bob can force a fifth colour by considering, up to Θ-symmetry, the respective passing boards 1 3 2 4 2 1 3 4 and 1 3 4 4 2 3 1 2 .(17) Now, in both cases, Alice has to avoid the obliged use of a sixth colour. The only possibility to get it is using the fifth colour to give rise, up to Θ-symmetry, to the respective passing boards 1 3 2 4 2 1 5 3 5 4 and 1 3 4 4 2 3 5 1 5 2 .(18) Even if none of the two cases forces the colour of all the cells, it is not difficult to see that Alice wins both games without the requirement of a sixth colour. ii. Suppose now, after Bob’s first move, we have the second passing board in (9). In order to avoid the use of six colours, the only winning strategy of Alice would be to colour one of the cells (1,4) or (2,3) with the colour 3 or 4, respectively. Then, an optimal move for Bob would be to force a fifth symbol by colouring one of the cells (3,2) or (4,1) with the colour 4 or 3, respectively. After these two moves, the resulting passing board would be, up to Θ-symmetry, 1 3 2 4 4 1 3 2 (19) In order to avoid the requirement of using a sixth symbol, Alice has to colour one of the cells (1,2), (2,1), (3,4) or (4,3) with the colour 5. After that, the colouring of the remaining cells from a palette of five colours is forced. iii. Starting from the third passing board in (9), a simple study of cases enables us to ensure the requirement of a fifth symbol to get a winning strategy for Alice. However, she can follow a strategy to avoid the use of a sixth colour. A possible series of alternate best Alice’s and Bob’s moves to get it is 1 2 3 4 → 1 2 2 1 3 4 → 1 4 2 321 3 4 → 1 4 2 3 2 1 5 3 5 4 Alice’s move Bob’s move Alice’s move .(20) 208 iv. From the fourth passing board in (9), any possible move of Alice, together with the next best one of Bob, gives rise, up to Θ-symmetry, to one of the following two situations. 1 2 2 1 → 1 3 2 4 2 1 → 132 4 2 1 4 3 Alice’s move Bob’s move (21) 1 2 2 1 → 1 2 2 1 1 2 → 1 2 2 1 3 1 4 2 Alice’s move Bob’s move (22) In both cases, a fifth colour is required. The only possibility that Alice has in order to avoid the obliged use of a sixth colour is using the fifth colour to give rise, up to Θ-symmetry, to the respective passing boards 1 3 2 4 2 1 5 4 5 3 and 1 2 5 2 5 1 3 1 4 2 .(23) v. Finally, in case of dealing with the fifth passing board in (9), the next moves of Alice and Bob give rise, up to Θ-symmetry, to one of the two following passing boards. 1 4 3 3 2 4 1 2 and 1 3 2 4 4 1 3 2 (24) Again, a fifth colour is required in both cases. Alice avoids the requirement of using a sixth colour by giving rise, up to Θ-symmetry, to the respective passing boards 1 4 3 3 2 4 5 1 5 2 and 1 3 5 2 5 4 4 1 3 2 .(25) (g) Suppose Θ=((12)(34),(12)(34),Id) ∈I4. If it is Alice who starts the game, then Bob’s next move, together with the next best one of Alice, gives rise, up to Θ-symmetry, to one of the following two passing boards. 1 2 2 1 1 1 and 1 2 1 2 1 1 (26) In both cases, Bob can force the use of a fifth colour once he gives rise, respectively, to the passing boards 1 2 2 1 1 3 3 1 and 1 2 1 2 2 1 2 1 .(27) The necessity of the fifth colour in the first case is clear. In the second case, once Alice colours a cell of one of the empty cell orbits with a third symbol, Bob colours with the fourth colour one of the cells of the empty cell orbit within the diagonal opposite Θ-block. A sixth symbol is not required in any case. On the other hand, if it is Bob who starts the game, Alice can use a so-called copy-cat strategy: she wins with a palette of four colours if she always replicates Bob’s move in the corresponding diagonal opposite Θ-block. We illustrate this fact by the