List and total colorings of multiset permutation graphs Abstract Let k k and ℓ \ell be positive integers. The multiset star transposition graph ST ℓ k {}_{k}^{\ell} has as vertices the k ​ ℓ k\ell -strings v 0 ⋯ v k ​ ℓ − 1 v_{0}\cdots v_{k\ell-1} on k k symbols, each symbol repeated ℓ \ell times, and edges given by the transpositions ( v 0 ​ v i ) (v_{0}\;v_{i}) with v i ≠ v 0 v_{i}\neq v_{0} ( 0 < i < k ​ ℓ 0 1 k>1 and ℓ > 2 \ell>2 that ST ℓ k {}_{k}^{\ell} is ( ℓ − 1 ) (\ell-1) -choosable and that, as a result, admits total colorings. In order to prove such assertions, the notion of efficient domination set (or E-set) of a graph is generalized for ℓ > 1 \ell>1 to that of an efficient dominating ℓ \,{}^{\ell} -set and applied to the graphs ST ℓ k {}_{k}^{\ell} , showing they admit vertex partitions that generalize the Dejter-Serra partitions of ST 1 k {}_{k}^{1} into E-sets, but not efficiently in the sense that the distance of each E ℓ -set be 3. Efficiently in such sense however, S ​ T k 2 ST^{2}_{k} and the related 2-set pancake permutation graph PC k 2 {}^{2}_{k} , among other intermediate permutation graphs, are shown to admit total colorings with 2 ​ k − 1 2k-1 colors that determine partitions into 2 ​ k − 1 2k-1 E-sets, each with distance 3. Furthermore, associated E-chains are examined. Italo J. Dejter University of Puerto Rico Rio Piedras, PR 00936-8377 italo.dejter@gmail.com 1 Introduction Let 01 , then v is the only vertex of G in the intersection of the 1-spheres of v^{0},v^{1},\ldots,v^{\ell-1} . Since the girth of G is required to be larger than 3, the dominating \,{}^{\ell} -set (or D \,{}^{\ell} -set ) S(v)=\{v^{0},v^{1},\ldots,v^{\ell-1}\} of v with respect to (or wrt ) S is an independent subset of G . Clearly, an E \,{}^{\ell} -set S of G is the union of the D \,{}^{\ell} -sets wrt S . In particular, if \ell=1 then S is a 1-perfect code (or 1-error correcting code ) [ 6 , 10 , 18 , 22 , 21 ] , also said to be an efficient dominating set (or E-set ) [ 1 , 2 , 3 , 11 , 12 , 17 ] . Example 1 . Here is an example of what is not an efficient dominating set: Let X=\{w_{0},w_{1}\} and Y=\{v,v^{\prime},v^{\prime\prime}\} be the vertex parts of the bipartite graph G=K_{2,3} . Then, the stable set S(v)=X is not a 2-efficient dominating set of G because the intersection of the 1-spheres of w_{0} and w_{1} is all of Y , not a sole vertex, as required in the definition above. Combined with total coloring, (whose definition is recalled shortly below), E \,{}^{\ell} -sets are addressed in Sections 2 – 3 and its sub-case \ell=2 in Sections 4 – 9 , in extending results of [ 11 ] and [ 9 ] . The present treatment considers the multiset star transposition graphs introduced in Section 2 and their pancake permutation graph variation in Section 9 , among others. In Sections 4 - 5 , these multiset cases are shown to lead to list-coloring [ 13 , 19 , 28 ] applications. Other applications of E \,{}^{\ell} -sets occur in the Theory of Error-Correcting Codes [ 18 , 21 , 22 ] . A total coloring (or TC ) of a graph G is an assignment of colors to the vertices and edges of G such that no two incident or adjacent elements (vertices or edges) are assigned the same color [ 15 ] . The TC Conjecture , posed independently by Behzad [ 4 , 5 ] and Vizing [ 27 ] , asserts that the total chromatic number \chi^{\prime\prime}(G) of a graph G (namely, the least number of colors required by a TC of G ) is either \Delta(G)+1 or \Delta(G)+2 , where \Delta is the largest degree of any vertex of G . A recent survey [ 15 ] contains an updated bibliography on TCs following the previous account of [ 29 ] . The TC Conjecture was established for cubic graphs [ 14 , 7 , 23 , 26 ] , meaning that the total chromatic number of cubic graphs is either 4 or 5. To decide whether a cubic graph G has total chromatic number \Delta(G)+1 , even for bipartite cubic graphs, is NP-hard [ 24 ] . A total coloring of a k -regular graph G such that the vertices adjacent to each v\in V(G) together with v itself are assigned pairwise different colors of the color set [k]=\{0,1,\ldots,k-1\} will be said to be an efficient coloring if each v\in V(G) together with its neighbors are assigned all the colors of [k] . However, this is not a property suitable for E ℓ -sets, as the minimum distance of each E ℓ -set is 2, not 3. The study of efficient colorings was considered in [ 8 ] and [ 9 ] for k -regular graphs with k+1 colors. 2 Multiset star transposition graphs Let 0<\ell\in\mathbb{Z} and let 11 (which excludes ST^{1}_{1} ) is the Cayley graph of Sym_{k} with respect to the set of transpositions \{(0\;i);i\in[k]\setminus\{0\}\} . Such a graph is denoted ST_{k} in [ 1 , 11 ] , where is proven that its vertex set admits a partition into k E-sets, exemplified on the upper left of Figure 1 for ST^{1}_{3}=ST_{3} , with the vertex parts of the partition differentially colored in blue, red and green, for first entries 0, 1 and 2, respectively. Figure 1 of [ 11 ] shows a similar example for ST^{1}_{4}=ST_{4} . Also, the graph ST^{2}_{k} is vertex transitive, but is not a Cayley graph; it is neither a Schreier graph with respect to the subgroup specified in Remark 26 ; (even though every regular graph can be presented as a Schreier graph). Let k>1 . We consider in Section 3 , for each i\in[k] , among the vertices v=v_{0}\dots v_{k\ell-1} of ST^{\ell}_{k} , those that have the first entry v_{0} equal to i and find they form an E \,{}^{\ell} -set S=S_{i}^{k} of ST^{\ell}_{k} , to be said to be an SE \,{}^{\ell} -set . In addition, we consider in Sections 7 - 9 the sets \Sigma_{i}^{k} of vertices v_{0}v_{1}\cdots v_{2k-1} of ST^{2}_{k} such that v_{0}=v_{i} for exactly one value i=1,\ldots,2k-1 , as there are just two occurrences of each symbol in every vertex of ST^{\ell}_{k} . In preparation, Sections 4 - 5 shows, for k>1 , that 1. if \ell>1 , then ST_{k}^{\ell} has a total coloring; 2. if \ell>2 , then ST_{k}^{\ell} is (\ell-1) -choosable; 3. ST_{k}^{2} has an efficient coloring via the sets \Sigma_{i}^{k} , to be referred to as \Sigma E-sets . Theorem 15 (Section 6 ) is a structural result for efficient colorings of ST_{k}^{2} as in item 3. Let \ell\in\{0,1\} . In Subsection 8 we generalize, by means of \ell -set permutations (see Section 2 ), the result of [ 11 ] that the star transposition graphs form a dense segmental neighborly E-chain . In Section 9 we generalize multiset star transposition graphs to multiset pancake permutation graphs and related intermediate graphs [ 11 ] leading to a suitable version of dense neighborly E-chain with obstructions preventing segmental E-chains. 3 SE \,{}^{\ell} -sets of \ell -set star transposition graphs The vertices of ST^{\ell}_{k} are the multiset permutations v_{0}\dots v_{k\ell-1} of the string \overbrace{0\cdots 0}\overbrace{1\cdots 1}\overbrace{2\cdots 2}\cdots\overbrace{(k-1)\cdots(k-1)}=0^{\ell}1^{\ell}2^{\ell}\cdots(k-1)^{\ell}. For each i\in[k] , among the vertices v=v_{0}\dots v_{k\ell-1} of ST^{\ell}_{k} , let us show that those that have the first entry v_{0} equal to i constitute an SE \,{}^{\ell} -set S=S_{i}^{k} of ST^{\ell}_{k} . Theorem 2 . Let 0<\ell,k\in\mathbb{Z} and let ST^{\ell}_{k}\neq ST^{1}_{2} . For each i\in[k] , the multiset permutations v_{0}\dots v_{k\ell-1} of the string 0^{\ell}1^{\ell}2^{\ell}\cdots(k-1)^{\ell} that have their first entry v_{0} equal to i constitute an SE \,{}^{\ell} -set S_{i}^{k} of the graph ST^{\ell}_{k} . Each D \,{}^{\ell} -set wrt S_{i}^{k} is an independent set of ST^{\ell}_{k} . Proof. For fixed i\in[k] , each vertex v=v_{0}v_{1}\cdots,v_{k\ell-1} of E(ST^{\ell}_{k})\setminus S_{i}^{k} has initial entry v_{0}=j , for some j\in[k] such that j\neq i . Then, v is adjacent to \ell vertices of S_{i}^{k} obtained by transposing the position of each of the \ell entries v_{h}=i with the position of that initial entry v_{0}=j , where h\in\{1,\ldots,k\ell-1\} . The graph induced by the edges of such adjacencies form a copy H of the complete bipartite graph K_{1,\ell} with v as its sole degree- \ell vertex and its leaves (if H is taken as a rooted tree with v as its root) as the vertices v^{j} in S_{i}^{k} obtained from v by transposing v_{0}=j with the entries v_{h}^{j}=i of those vertices. Since ST^{\ell}_{k}\neq ST^{1}_{2} has girth larger than 3, then each D \,{}^{\ell} -set wrt S_{i}^{k} is an independent set of ST^{\ell}_{k} . ∎ Corollary 3 . The vertex set V(ST^{\ell}_{k}) admits a partition into k SE \,{}^{\ell} -sets S_{i}^{k} , where i\in[k] . Proof. The SE \,{}^{\ell} -sets S_{i}^{k} form a partition of V(ST^{\ell}_{k}) , since each such S_{i}^{k} is composed precisely by the vertices v=v_{0}v_{1}\cdots v_{k\ell-1} of ST^{\ell}_{k} having initial entry v_{0}=i , which form precisely one of the k parts of the partition. ∎ Let 2ST^{\ell}_{k} be the multigraph obtained from ST^{\ell}_{k} by replacing each edge e of ST^{\ell}_{k} by two parallel edges with the same endvertices of e . Corollary 4 . Let i\in[k] . Each vertex of S_{i}^{k} belongs to k\ell-1 D \,{}^{\ell} -sets wrt S_{i}^{k} , where the induced graph of each D \,{}^{\ell} -set is isomorphic to the complete bipartite graph K_{1,\ell} . The set of all such D \,{}^{\ell} -sets, for every i\in[k] , form a partition of the edge set of 2ST^{\ell}_{k} . Figure 1: Colorings of ST_{3}^{1}=ST_{3} , ST_{2}^{2} (twice) and the Desargues graph ST_{2}^{3} . Proof. Since there are k-1 values j\neq i in [k] , each vertex v\in S_{i}^{k} belongs to k\ell-1 D \,{}^{\ell} -sets wrt S_{i}^{k} . Since each such v is the neighbor of \ell vertices with first entry v_{0}=j , for each j\in[k] with j\neq i , then the induced graph of each D \,{}^{\ell} -set is isomorphic to K_{1,\ell} , noted already in the proof of Theorem 2 . Also, each edge e of ST^{\ell}_{k} with endvertices v and w having respective first entries i and j is both a member of S_{i}^{k} and of S_{j}^{k} . Thus, e appears in 2ST^{\ell}_{k} as two parallel edges e^{i} and e^{j} in the respective induced subgraphs of S_{i}^{k} and S_{j}^{k} . ∎ Corollary 5 . If k=2 , each S_{i}^{k}=S_{i}^{2} as in Theorem 2 induces an edge partition P(S_{i}^{2}) of ST^{\ell}_{2} whose monochromatic components are copies of K_{1,\ell} in ST_{2}^{\ell} . Proof. For each fixed i=0,1 , the copies of K_{1,\ell} induced by the D \,{}^{\ell} -sets S_{i}^{2}(v) wrt S_{i}^{2} form a partition of the edge set of ST^{\ell}_{2} whose monochromatic components are precisely such copies. ∎ Example 6 . Here are two examples of SE \,{}^{\ell} -sets, for \ell=2,3 , where elements of SE \,{}^{\ell} -sets appear underlined in the accompanying Figure 1 . The graph ST_{2}^{2} is the 6-cycle graph (0011,1001,0101,1100,0110,1010) , represented in the middle left of Figure 1 and showing in distinct edge shades the induced subgraphs of the composing D 2 -sets of the SE \,{}^{2} -set S=\{0011,0101,0110\} , namely the D 2 -set \{0011,0101\} of 1001 wrt S , the D 2 -set \{0011,0110\} of 1010 wrt S , and the D 2 -set \{0110,0101\} of 1100 wrt S . The graph ST_{2}^{3} is the Desargues graph on the right of Figure 1 , where the subgraphs K_{1,3} induced by the D 3 -sets S_{0}^{2}(v) of the vertices v=1v_{1}\cdots v_{5} of ST_{2}^{3} wrt S_{0}^{2} have the edges in red, blue, green, hazel and violet, in order to differentiate them. These subgraphs K_{1,3} appear in “opposing” pairs, allowing to raise the question of how many colors are necessary to color such edge partitions. Example 7 . The vertices of ST_{3}^{2} are the multiset permutations of v_{0}^{0}=001122 , a total of |V(ST_{3}^{2})|=\frac{6!}{2!2!2!}=\frac{720}{8}=90 vertices. The regular degree of ST_{3}^{2} is 4. The graph ST^{3}_{2} has the SE 3 -set S_{0}^{2}=\{v_{0}\cdots v_{5}\in V(ST(_{3}^{2});v_{0}=0\} . For example, v=100122 has S^{k}_{0}(v)=S^{2}_{0}(v)=\{010122,001122\} as its D \,{}^{\ell} -set wrt S , and v^{\prime}=120120 has S^{k}_{0}(v^{\prime})=S^{2}_{0}(v^{\prime})=\{021120,020121\} as D \,{}^{\ell} -set wrt S_{0}^{2} . Each vertex v in S_{0}^{2} belongs to k\ell-1=4 D 2 -sets wrt S_{0}^{2} . While ST_{3}^{2} has 90 vertices, S has \frac{90}{k}=\frac{90}{3}=30 vertices. For example, 010122 belongs to S^{2}_{0}(100122) , S^{2}_{0}(110022) , S^{2}_{0}(210102) and S^{3}_{0}(210120) . Specifically as in display ( 7 ). \displaystyle\begin{array}[]{ccc}S_{0}^{3}(100122)=\{010122,001122\},\\ S_{0}^{3}(110022)=\{010122,011022\},\\ S_{0}^{3}(210102)=\{010122,012102\},\\ S_{0}^{3}(210120)=\{010122,012120\}.\end{array} 4 List coloring of \ell -set star transposition graphs Theorem 8 . Let k>0 and let \ell>1 . Then, the graph ST_{k}^{\ell} has a proper edge coloring. Figure 2: On 2-choosability of the Desargues graph ST_{2}^{3} . Proof. A proper edge coloring of ST_{k}^{\ell} is given as follows. Let i\in[k\ell]\setminus\{0\} . Then, each edge \displaystyle(v,w)=(v_{0}v_{1}\cdots v_{i}\cdots v_{k\ell-1},\;v_{i}v_{1}\cdots v_{0}\cdots v_{k\ell-1}),\mbox{ where }v_{i}\neq v_{0},\mbox{ is assigned color }i. (6) The resulting edge color assignment also is to include that the edge \displaystyle\begin{array}[]{ll}(v,w)=(v_{0}v_{1}\cdots v_{k\ell-1},\;v_{1}v_{0}\cdots v_{k\ell-1}),\mbox{ where }v_{1}\neq v_{0},&\mbox{ is assigned color }1,\mbox{ and}\\ (v,w)=(v_{0}v_{1}\cdots v_{k\ell-1},\;v_{k\ell-1}v_{1}\cdots v_{0}),\mbox{ where }v_{2k-1}\neq v_{0},&\mbox{ is assigned color }k\ell-1.\end{array} As a result, the edges incident to each vertex of ST_{k}^{\ell} have pairwise different colors, so that ST_{k}^{\ell} has a proper edge coloring. ∎ Given a graph G and a color subset (said to be a list ) L(v) , \forall v\in V(G) , a list coloring of G is a function \lambda that maps every v\in V(G) to a color \lambda(v)\in L(v) [ 13 , 19 , 25 , 28 ] . Such list coloring is proper if no two adjacent vertices get the same color. A graph is k - choosable if it has a proper list coloring, no matter how one assigns a list of k colors to each vertex. Theorem 9 . Let k>1 and let \ell>2 . Then, the graph ST_{k}^{\ell} is (\ell-1) -choosable. However, no (\ell-1) -list coloring of ST_{k}^{\ell} contains only efficient color classes. Proof. There are \ell-1 occurrences of the first entry v_{0} in any vertex v=v_{0}\cdots v_{k\ell-1} of ST_{k}^{\ell} . The remaining (k-1)\ell entries in \{1,\ldots,k\ell-1\} determine the edges incident to v ; these edges are colored according to displays ( 6 ) and ( 4 ). The said \ell-1 occurrences constitute a list L(v) , \forall v\in V(ST_{k}^{\ell}) . Adjacent vertices v=v_{0}\cdots v_{k\ell-1} and w=w_{0}\cdots w_{k\ell-1} have L(v)\cap L(w)=\emptyset , since v_{0}\neq w_{0} , where w_{0}=v_{j} for some j\in\{1,\dots,k\ell-1\} and v_{j}\neq v_{0} , that is: v_{j} must have a different value in \{0,\ldots,k-1\} than that of v_{0} . Thus, ST_{k}^{\ell} is (\ell-1) -choosable. To show that no (\ell-1) -list coloring of ST_{k}^{\ell} contains only efficient color classes, note that each vertex w at distance 2 from say vertex v=00\cdots 0v_{\ell}\cdots,v_{k\ell-1} starts with w_{0}=0 and only has one entry in \{w_{1},\ldots,w_{\ell-1}\} distinct from 0. But there are (\ell-1)(\ell-2) such vertices w and only \ell-1 colors availabe, so by the Pigeonhole Principle, the last sentence of the statement holds in this case. A similar argument holds by setting v_{0}\neq 0 and taking any permutation of the remaining entries of v . ∎ Example 10 . The Desargues graph ST_{k}^{\ell}=ST_{2}^{3} is 2-choosable according to Theorem 9 and the lists L(v) are deduced on the left of Figure 2 from the colored (not light-gray) positions of the tuples representing the corresponding vertices v . Any list coloring associated to this is proper, as for example the one shown on the right of the figure. However, there is no (\ell-1) -list coloring containing only efficient color classes, as verifiable on the figure, where on the right side there are pairs of vertices at distance 2 with a common color. 5 Total coloring of \ell -set star transposition graphs Theorem 11 . Let k>1 and let \ell>1 . Then, the graph ST_{k}^{\ell} has a total coloring. Proof. For \ell>2 , the proper edge coloring of Theorem 8 and any list selection of a proper vertex coloring as in Theorem 9 constitute a total coloring of ST_{k}^{\ell} , since the positions of the entries used for any vertex v and its neighbors are pairwise different, and the positions of the entries used for v and its incident edges are also pairwise different. The case \ell=2 only differs from that in the previous paragraph in that the list L(v) of each vertex v of ST_{k}^{\ell}=ST_{k}^{2} has just one color, so choosability is not properly applicable. Such only color differs from the colors of its adjacent vertices, that have pairwise different colors, and differs from the colors of its incident edges, that also have pairwise different colors, so a total coloring also exists in this case. ∎ Theorem 12 . Let k>1 . Then, the graph ST_{k}^{2} has an efficient coloring via the \Sigma E \,{}^{2} -sets \Sigma_{i}^{k} mentioned in item (3) in Section 2 . Proof. The Pigeonhole Principle, as applied in the proof of Theorem 9 , cannot be applied properly in this case \ell=2 , where the SE ℓ -sets S_{i}^{k} are used however yielding an efficient coloring. But employing the sets \Sigma_{i}^{k} , we find that there are two types of colored 6-cycles in a total coloring of ST_{k}^{2} , illustrated in Figure 3 (see Example 13 below), namely 1. 6-cycles, denoted C(c_{1},c_{2},c_{3}) , having three pairs of opposite edges, where each pair has its two edges with the same color, a total of three colors c_{1},c_{2},c_{3} ; 2. 6-cycles, denoted C(d_{1},d_{2}) , having two triples of independent edge of alternate colors d_{1},d_{2} . For any 6-cycle C=C(c_{1},c_{2},c_{3}) of type 1 and each color d\notin\{c_{1},c_{2},c_{3}\} , the six edges of color d with just one endvertex in C have their remaining six endvertices at pairwise distance 3 between them. This is the only way to get vertices of a common color in ST_{k}^{2} , at pairwise distance 3, and such vertices form part of a \Sigma E-set of ST_{k}^{\ell} by means of the same (continued) argument presented so far. In fact, those six edges of color d determine six triples of independent color- d edges in six corresponding 6-cycles C^{\prime} of type 2 adjacent to C . In each such C^{\prime} , the remaining triple of independent edges separates C^{\prime} not only from C but from two other 6-cycles of type 1, fact useful in continuing the formation of the \Sigma E-sets. ∎ Example 13 . Figure 3 represents two embeddings of a 6-cycle C=C(2,3,4) of type 1 (forming the inner border of an annular gray area, darker on the left, lighter on the right) in ST_{3}^{2} surrounded by two different sextuples of 6-cycles of type 2, where colors are numbered 1 = red, 2 = blue, 3 = green, 4 = hazel and 5 = black. On the left, (resp. right), representation of the figure, the six (underlined) vertices at distance 1 from C (on the external border of the annular gray area) have color 5 = black, (resp. 1 = red), realized by edges of color 1 = red, (resp. 5 = black). Clearly, the distance between the underlined vertices is 3. Corollary 14 . In ST_{k}^{2} for fixed k>2 , the union of all 6-cycles of the form C(d_{1},d_{2}) , C(d_{1},d_{3}) , C(d_{1},d_{4}) , C(d_{1},d_{5}) of type 2 with independent edge triples sharing common color d_{1} , where the colors d_{i} are pairwise different ,for i=1,2,3,4,5 , form toroidal subgraphs T_{d_{1}}(d_{2},d_{3},d_{4},d_{5}) containing the disjoint union of cycles C(c,c^{\prime},c^{\prime\prime}) of type 1, ( \{c,c^{\prime},c^{\prime\prime})\subset\{d_{2},d_{3},d_{4},d_{5}\} ), with minimum distance 1 produced by edges of color d_{1} . Moreover, from each such C(c,c^{\prime},c^{\prime\prime}) depart six edges having the left color d\in\{d_{2},d_{3},d_{4},d_{5}\}\setminus\{c,c^{\prime},c^{\prime\prime}\} with the remaining endvertices belonging to the E-set \Sigma_{d_{1}}^{k} of vertices with color d_{1} . Figure 3: Example for the proof of Theorem 12 and Example 13 . Proof. The proof is shown here for k=3 and d_{1}=5 . The general case works likewise. The E-set \Sigma_{d_{1}}^{k} is given as the set of vertices v=d_{1}v_{1}v_{2}v_{3}v_{4}d_{1} of degree 1 in the toroidal subgraph T_{5}(1,2,3,4) obtained from the rectangular cutout shown in Figure 4 by identifying the top and bottom borders, with the bottom border displaced half its length to the right with respect to the top border, (as shown by the displacement between the two parts of the light-gray area, redrawn here from the one in Figure 3 , as is the dark-gray area, too) and identifying in parallel the left and right borders. Inside each C(c,c^{\prime},c^{\prime\prime}) , a pair d_{1}v_{i} is highlighted, where v_{i} must be transposed with the initial d_{1} in order to transform each vertex v into its adjacent vertex in the 6-cycle C(c,c^{\prime},c^{\prime\prime}) , ( d_{1}\in\{0,1,2\} , v_{i}\in\{1,2,3,4\} ). Only a few (underlined) ”black” vertices v=d_{1}v_{1}v_{2}v_{3}v_{4}d_{1} are specified in the figure, but all the otherwise colored vertices are. ∎ 6 Efficient coloring of 2-set star transposition graphs In Theorem 12 , it was shown that the graphs G=ST^{2}_{k} , ( 04 , leaves us with the graph induced by the edges of all colors other than color i , which necessarily disconnects G\setminus W_{i} , again because of the definition of efficient coloring. To establish item 2, the removal of the edges with color i leaves their endvertices with degree h-3 and forming a vertex subset of the resulting G\setminus E_{i} , while the remaining vertices have color i , degree h-2 and form a stable vertex set. This completes the proof of the theorem. ∎ Example 17 . The odd complete graphs K_{2n+1} ( n\geq 1 ) satisfy the conditions of Theorem 15 with h=n+1 , but does not satisfy our initial assumption that the girth be larger than 3. In fact, a total coloring [ 29 ] of K_{2n+1} is given by numbering the vertices 0,1,\ldots,2n so that the edges (j-i)(j+i) with j\in\{0,\ldots,2n\} get color j while each vertex j gets precisely color j , where 01 . As said at the end of Section 2 , we consider here only the graphs ST^{2}_{\ell} and their vertex subsets \Sigma_{i}^{k} formed by the vertices v_{0}v_{1}\cdots v_{2kl-1} such that v_{0}=v_{i} for exactly one value i\in\{1,\ldots,2k-1\} . We notice that the graph ST^{2}_{k} has \frac{(2k)!}{2^{k}} vertices and regular degree 2k-2 . Theorem 18 . Let i\in[2k]\setminus\{0\}=\{1,\cdots,2k-1\} and let \Sigma_{i}^{k} be the set of vertices v_{0}v_{1}\cdots v_{2k-1} of ST^{2}_{k} such that v_{0}=v_{i} , where i=1,\ldots,2k-1 . Then, the 2k-1 sets \Sigma_{i}^{k} are \Sigma E-sets forming a partition of V_{k}^{2}=V(ST^{2}_{k}) . Proof. The sets \Sigma_{i}^{k} are \Sigma E-sets, since every vertex of V_{k}^{2}\setminus\Sigma_{i}^{k} is a neighbor of just one vertex of \Sigma_{i}^{k} , for each i\in[2k]\setminus\{0\} . In fact, every vertex v\in V_{k}^{\ell}\setminus\Sigma_{i}^{k} is either of the form v_{0}\cdots v_{i}\cdots v_{j}\cdots v_{2k-1} or v_{0}\cdots v_{j}\cdots v_{i}\cdots v_{2k-1} with v_{i}=v_{j} . Applying the transposition (0\;j) to v yields a neighbor of v in \Sigma_{i}^{k} . Moreover, the sets \Sigma_{i}^{k} form a partition of V_{k}^{2} , since each \Sigma_{i}^{k} is the set of vertices v_{0}v_{1}\cdots v_{k\ell-1} of ST^{2}_{k} with v_{0}=v_{i} , for i=1,\ldots,2k-1 . ∎ Theorem 19 . Let k>2 and let i\in[2k]\setminus\{0\} . Let E_{i}^{k} be the set of edges having color i in G\setminus\Sigma_{i}^{k} , provided by Theorem 8 . Then, no edge of E_{i}^{k} is incident to any vertex of \Sigma_{i}^{k} . Proof. Corollary 14 and Figure 4 offer a case of the statement for d_{1}=v_{2k-1} , as all the (black) edges (v,w) of color 2k-1 are obtained by permuting the first and last entries of v and w , while a vertex u of color 2k-1 has the first and last entries with the same color, preventing u to be the endvertex of color 2k-1 . ∎ Example 20 . In ST_{2}^{2} , \Sigma_{1}^{2} , depicted in the lower left of Figure 1 as the 6-cycle induced by the external thick (not thin) edges, has an efficient coloring with \Sigma_{1}^{2}=\{0011,1100\} in color blue, as is also E_{1}^{2}=\{(0101,1001),(0110,1010)\} ; \Sigma_{2}^{2}=\{0101,1010\} in color green, as is also E_{2}^{2}=\{(0110,1100),(0011,1001)\} ; \Sigma_{3}^{3}=\{0110,1001\} in color red, as is also E_{3}^{2}=\{(0011,1010),(0101,1100)\} . (The thin edges appear in Example 22 ). Theorem 21 . The partitions into \Sigma E-sets \Sigma_{i}^{k} of the graphs ST^{2}_{k} , for i\in[2k]\setminus\{0\} , extend to partitions into \Sigma E-sets of supergraphs of the graphs G=ST^{2}_{k} , but such partitions cannot be completed into efficient colorings. Proof. Let G=ST^{2}_{k} and let h=2k . In the setting of Theorem 15 , let W_{i}=\Sigma_{i}^{k} , for i\in[h]\setminus\{0\} . Let us number the vertices of W_{i} , for i\in[h]\setminus\{0\} , by writing W_{i}=\{w_{i}^{1},\ldots,w_{i}^{t}\} , where t=|W_{i}| is the common cardinality of the classes W_{i} . Let us add to G vertices i=1,\ldots,t , with the new vertex i made adjacent to each vertex in \{w_{i}^{1},\ldots,w_{i}^{t}\} . We add a new color h\notin[h]\setminus\{0\} for the new vertices 1,\ldots,t . This way, the resulting graph has a partition into \Sigma E-sets, but not an efficient coloring. In fact, the new edges adjacent to the new vertex i\in\{1,\ldots,t\} should have pairwise different colors for the resulting coloring to be total, which is not the case since all colors in \{2,\ldots,h-1,h\} were employed already, a contradiction. ∎ Example 22 . To illustrate Theorem 21 , the graph ST_{2}^{2} depicted on the lower left of Figure 1 for Example 20 has two additional central vertices 1 and 2 and six new thin edges from W_{1}=\{0011,0101,0011\} onto vertex 1 and from W_{2}=\{1100,1010,1001,1100\} onto vertex 2, leading to complete the 6-cycle ST_{2}^{2} into an image of the 3-cube and exemplifying the observed contradiction. Remark 23 . The total coloring of ST^{2}_{k} will be referred to as its color structure . The k2^{k-1} copies of ST^{2}_{k-1} in ST^{2}_{k} whose disjoint union is ST^{2}_{k}\setminus\Sigma_{i}^{k}\setminus E_{i}^{k} inherit each a color structure that generalizes that of the 3-colored 6-cycles in ST^{2}_{3}\setminus\Sigma_{5}^{3} and is similar to the color structure of ST^{2}_{k-1} . Theorem 24 . The graphs ST^{2}_{k} satisfy the conditions of Theorem 15 , so they also satisfy its conclusions. Proof. Let us see that the hypotheses of Theorem 15 are satisfied by taking h=2k , G=ST^{2}_{k} , W_{i}=\Sigma_{i}^{k} and E_{i}=E_{i}^{k} , where i\in[h]\setminus\{0\} . Then, it is seen that ST^{2}_{k}\setminus W_{i} is a connected (h-3) -regular subgraph such that at most h-1 colors are required for it to have an efficient coloring. Moreover, Theorems 18 and 19 imply item 1. Furthermore, item 2 holds, since clearly ST^{2}_{k}\setminus E_{i} is a non-bipartite (h-2,h-3) -biregular graph, as the vertices of W_{i} have degree h-2 in ST^{2}_{k} while the remaining vertices, having each lost the adjacency of an edge of E_{i} , have degree h-3 . ∎ 8 SE- and \Sigma E-chains of 2-set star transposition graphs In [ 11 ] , a countable family of graphs {\mathcal{G}}=\{\Gamma_{1}\subset\Gamma_{2}\subset\cdots\subset\Gamma_{i}\subset\Gamma_{i+1}\subset\cdots\} was said to be an E-chain if every \Gamma_{i} was an induced subgraph of \Gamma_{i+1} and each \Gamma_{i} had an E-set C_{i} , for 01 the graph ST^{1}_{k} is the Cayley graph of Sym_{k} generated by the transpositions (0\;i) , ( 01 the graph ST^{\ell}_{k} is neither a Cayley graph nor a Schreier coset graph of the quotient of Sym_{k\ell} modulo say its subgroup H_{\ell} generated by the transpositions (i\;i+1) , ( 0\leq i2 , extend the definition of a Schreier coset graph as said above. The example in display 8 shows that ST^{2}_{2} is a Schreier local coset graph of the group V(ST^{1}_{4}) , its subgroup H generated by the transpositions (0\;1) and (2\;3) , and the local generators indicated in the last line of the display. This shows downward from the top the right cosets of V(ST^{1}_{4}) mod the subgroup generated by the transpositions (0\;1),(2\;3) , and then the representations of such right cosets as vertices of ST^{2}_{2} . \displaystyle\begin{array}[]{l||c|c|c|c|c|c}Right&0123&2301&0213&2031&0231&2013\\ cosets\;of&0132&2310&0312&2130&0321&2103\\ V(ST^{1}_{4})&1023&3201&1203&3021&1230&3012\\ mod\;H&1032&3210&1302&3120&1320&3102\\ \hline\cr V(ST^{2}_{2})&0011&1100&0101&1010&0110&1001\\ \hline\cr Gen.\;set&(0\;2),(0\;3)&(0\;2),(0\;3)&(0\;1),(0\;3)&(0\;1),(0\;3)&(0\;1),(0\;2)&(0\;1),(0\;2)\\ \end{array} In a similar way, it is seen for k>2 that ST^{2}_{k} is a Schreier local coset graph of V(ST^{2}_{k}) with respect to the subgroup generated by the transpositions (2a\;2a+1) with 0\leq a2 , let \pi_{i} be an any product of independent transpositions of the set \{1,\ldots,i-1\} . Let A(\pi_{1},\ldots,\pi_{i},\ldots,\pi_{2k-1})=\{(0\;1)\pi_{1},\ldots,(0\;i)\pi_{i},\ldots,(0\;2k-1)\pi_{2k-1}\}. In [ 11 , Lemma 2] it is implied that for any choice of the permutations \pi_{i} , for i\geq 3 , the set A(\pi_{1},\ldots,\pi_{2k-1}) generates Sym_{2k-1} , so the sequence of Cayley graphs with generating set A(\pi_{1},\ldots,\pi_{2k-1}) forms a chain of nested graphs {\mathcal{G}}=\{\Gamma_{1}\subset\Gamma_{2}\subset\cdots\subset\Gamma_{k}\subset\Gamma_{k+1}\subset\cdots\} with natural inclusions \Gamma_{k}\subset\Gamma_{k+1} . If we choose \pi_{1}=\pi_{2}=\cdots=\pi_{2k-1} in A(\pi_{1},\ldots,\pi_{2k-1}) , we get the \ell -set star transposition graphs ST^{\ell}_{k} and a resulting SE ℓ -chain {\mathcal{G}}={\mathcal{S}T}^{\ell} with \Gamma_{k}=ST^{\ell}_{k} . If we choose \pi_{i}=(1\;i-1)\cdots(\lfloor i/2\rfloor\;\lceil i/2\rceil) , for i=3,\ldots,k-1 , we get the \ell -set pancake permutation graph PC_{k}^{\ell} and a resulting SE ℓ -chain {\mathcal{G}}={\mathcal{P}C}^{\ell} . In particular, the \ell -set pancake permutation graph PC^{\ell}_{k} has the same vertex set as ST^{\ell}_{k} and its edges involve each the maximal product of concentric disjoint transpositions in any prefix of an endvertex string, including the external transposition (representing an edge of ST^{\ell}_{k} ). The graphs PC_{k}^{1} were seen in [ 11 ] to form a dense segmental neighborly E-chain \mathcal{PC}(1)=\{PC_{1}^{1},PC_{2}^{1},\ldots,PC_{k}^{1},\ldots\} . (Figure 2 of [ 11 ] represents the graph PC^{1}_{4} ). In a similar fashion to that of Section 8 , the following partial extension of that result can be established. Theorem 28 . The chain \mathcal{PC}(2)=\{PC_{1}^{2},PC_{2}^{2},\ldots,PC_{k}^{2},\ldots\} is a thick, disjoint neighborly \Sigma E-chain with the \Sigma E-sets \Sigma_{i}^{k} of Theorem 19 , but it fails to be disjoint segmental. A similar result is obtained for any choice of the involutions \pi_{1},\pi_{2},\ldots,\pi_{i}\ldots with not all the \pi_{i} s being identity permutations. Proof. Adapting the arguments given for {\mathcal{S}T}(2) in Subsection 8 can only be done for the \Sigma E-sets \Sigma_{i}^{k} in 2-set pancake permutation graphs, since the feasibility for the sets \Sigma_{i}^{k} , ( 1\leq i<2k-1 ), to be \Sigma E-sets is obstructed by the pancake permutations in A(\pi_{1},\ldots,\pi_{2k-1}) , meaning that we can only establish that the \Sigma E-chain \mathcal{PC}(2) is dense and disjoint neighborly, but not disjoint segmental. The “black’” vertices, those whose color is 2k-1 , form an \Sigma E-set \Sigma^{k}_{i} with the desired properties, and their removal leaves a 2k-2 -regular graph from which the removal of the “black” edges, forming an edge subset E^{2}_{i} , leaves the disjoint union of the open neighborhoods N(v) of the vertices v in the \Sigma E-set \Sigma^{k}_{i} . This behavior is similar for any other choice of the involutions \pi_{1},\pi_{2},\ldots,\pi_{i}\ldots with not all the \pi_{i} s being identity permutations, other than \pi_{i}=(1\;(i-1))\cdots(\lfloor i/2\rfloor\;\lceil i/2\rceil) , for i=3,\ldots,k-1 , which were used precisely to define the pancake permutation graphs. ∎