Let \(2\le k\in\mathbb{Z}\). We say that a total coloring of a \(k\)-regular simple graph via \(k+1\) colors is an efficient total coloring if each color yields an efficient dominating set, where the efficient domination condition applies to the restriction of each color class to the vertex set. We prove that Hamming shells of star transposition graphs and Hamming cubes have efficient total colorings. Also in this work, a focus is set upon the graphs of girth \(2k\) and \(k\). Efficient total colorings of finite connected simple cubic graphs of girth 6 are constructed. These are of two specific types, namely: (a) those whose 6-cycles use just 3 colors with antipodal monochromatic pairs of vertices or edges; (b) those whose 6-cycles do not respect item (a) so they use four colors. An orthogonality property holds for all graphs of type (a). Such property allows further edge-half-girth colorings in the corresponding prism graphs.
Given a simple connected graph \(\Gamma\), a total coloring or tC of \(\Gamma\) is a color assignment to the vertices and edges of \(\Gamma\) such that no two incident or adjacent elements (vertices or edges) are assigned the same color. A recent survey [12] contains an updated bibliography on tCs, with the tC Conjecture, posed independently by Behzad [1, 2] and by Vizing [19], that asserts that the total chromatic number of \(\Gamma\) (namely, the least number of colors required by a tC of \(\Gamma\)) is either \(\Delta(\Gamma)+1\) or \(\Delta(\Gamma)+2\), where \(\Delta\) is the largest degree of any vertex of \(\Gamma\).
The tC Conjecture was established for cubic graphs [4, 11, 16, 18], meaning that the total chromatic number of cubic graphs is either 4 or 5. To decide whether a cubic graph \(\Gamma\) has total chromatic number \(\Delta(\Gamma)+1\), even for bipartite cubic graphs, is NP-hard [17].
In [7], relations between total colorings of \(k\)-regular graphs of girth \(k+1\) (\(1<k\in\mathbb{Z}\)) and efficient dominating sets (EDSs) [6, 8, 9, 10, 13, 15] were established. Here, we establish similar relations for girths \(2k\) (Section 2) and \(k\) (Section 3), in place of \(k+1\). In fact, we prove that some star transposition graphs (Subsection 2.1), generalized Petersen graphs (Subsection 2.2), Hamming shells of star transposition graphs (Remark 1.8 and Subsection 2.3) and Hamming shells of Hamming cubes (Remark 1.9 and Subsection 3.1) have efficient total colorings. The following definition, given in [7], is employed.
Definition 1.1. [7] A coloring of a connected \(k\)-regular simple graph \(\Gamma\) (\(2\le k\in\mathbb{Z}\)) is said to be an efficient tC, or EtC, if:
(a) (tC condition) each \(v\in V(\Gamma)\) together with its neighbors are assigned all the colors in \([k+1]=\{0,1,\ldots,k\}\) via a bijection \(N[v]=N(v)\cup\{v\}\leftrightarrow[k+1]\), where \(N[v]\) and \(N(v)\) are the closed neighborhood of \(v\) and the open neighborhood of \(v\), respectively [8];
(b) the tC in item (a) partitions \(V(\Gamma)\) into \(k+1\) efficient dominating sets (EDSs), also called perfect codes, namely independent (stable) subsets \(S_i\subseteq V(\Gamma)\) such that for any \(v\in V(\Gamma)\setminus S_i\), \(|N[v]\cap S_i|=1\), where \(i\) varies in \([k+1]\), [6, 8, 9, 10, 13, 15].
Remark 1.2. Neither item (a) nor item (b) In Definition 1.1 involves how the edges are colored. This may come as a surprise to the reader since in fact we are dealing here with total coloring.
Under conditions (a)-(b), it is seen that the total chromatic number of \(\Gamma\) is \(\Delta(\Gamma)+1\).
Remark 1.3. For \(1<j\in\mathbb{Z}\), consider the \(6j\)-cycle graph \(C_{6j}=(v_1,e_1,v_2,e_2,\ldots,e_{6j-1},v_{6j},\) \(e_{6j})\), where \(e_i\) is the edge with end-vertices \(v_i\) and \(v_{i+1}\), for \(1\le i\le 6j-1\), and \(e_{6j}\) is the edge with end-vertices \(v_{6j}\) and \(v_1\). Let the successive vertices and edges of \(C_{6j}\) be together colored in one fixed direction of \(C_{6j}\) in the order of the colors in the color cycle \((0,1,2,0,1,2,\ldots,0,1,2)\). This clearly yields an EtC of \(C_{6j}\). For \(j=2\), this has girth 12.
In most of this work, finite connected simple \(k\)-regular graphs \(\Gamma\) (\(k\ge 2\)) of girth \(2k\) are dealt with. The purpose is to determine EtCs of such graphs. Some of these EtCs yield edge-half-girth colorings, (an adaptation of the edge-girth colorings of [7], see Definition 1.4, below) on the prism \(\Gamma\square K_2\), where \(K_2=P_2\) is the complete graph on two vertices, that is the path \(P_k\) consisting of \(k=2\) vertices.
Definition 1.4. Let \(\Gamma\) be a finite connected \(k\)-regular simple graph of girth \(2k\). An edge-half-girth coloring, or EhGC, of \(\Gamma\) is a proper edge coloring of \(\Gamma\) via \(k+1\) colors, each girth cycle colored with \(k\) colors, each color used precisely twice.
To present most of our results, we need every girth cycle \(C\) of \(\Gamma\) to be colored with at least \(k\) colors, each such color used at most twice on \(V(C)\). This leads to Definition 1.5, in which, in addition, the total coloring of the girth cycles is combined with the concept of EtC in Definition 1.1.
Definition 1.5. Let \(\Gamma\) be a connected simple \(k\)-regular graph of girth \(2k\).
(a) A vertex-edge partial-girth coloring, or VEpGC, of \(\Gamma\) is a tC in which the vertices of each girth cycle \(C\) are colored with at least \(k\) colors.
(b) An efficient partial-girth total coloring, or EpGtC, of \(\Gamma\) is an EtC that is VEpGC.
(c) If “at least” is removed from item 1 above, then we replace partial with half, so we use VEhGC and EhGtC instead of VEpGC and EhGtC, where h stands for half.
The results of Section 2 involve the existence of EhGtC’s and EpGtCs in finite connected simple \(k\)-regular graphs \(\Gamma\) of girth \(2k\). They also involve the existence of \(k\)-regular graphs \(\Gamma\) of corresponding EhGCs on the prisms \(\Gamma \square K_2\), for which we need Definition 1.6.
Definition 1.6. Given a connected simple graph \(\Gamma\) and a tC \(C\) of \(\Gamma\), if there exists a tC \(C'\) that coincides with \(C\) on \(V(\Gamma)\) but differs with \(E(\Gamma)\) edge by edge, i.e. \(C(e)\ne C'(e)\), \(\forall e\in E(\Gamma)\), then we say that \(C'\) is orthogonal to \(C\), or that \(C\) and \(C'\) form a pair of orthogonal tCs, so that they enjoy an orthogonality property.
Definition 1.7. [7] An \(\ell\)–belt in a plane graph \(\Gamma\) is a cycle bounding a face of \(\Gamma\) of length \(\ell\).
Below, efficient total colorings of finite connected simple cubic graphs of girth 6 are constructed. These are of two specific types, namely: (a) those whose 6-cycles use just 3 vertex colors with antipodal (distance 3) monochromatic vertex pairs; (b) those whose 6-cycles do not respect item (a), using in fact four vertex colors. Moreover, the orthogonality property of Definition 1.6 holds for all graphs of type (a). Such orthogonality property allows edge-half-girth colorings in the corresponding prism graphs.
In fact, Subsections 2.1 and 2.2 address EpGtCs in star transposition graphs [8] (type (a)), in some generalized Petersen graphs [4] (type b)) and in Hamming shells [5] of star transposition graphs [8] (type (a)), respectively. They also address EhGCs when they do exist on the corresponding prisms \(\Gamma\square K_2\). To refresh these concepts for the present purpose, we provide the following Remarks 1.8–1.9.
Remark 1.8. [8] Let \(2<n\in\mathbb{Z}\). The star transposition graph \(ST_n\) is the Cayley graph \(Cay(Sym_n,C)\), where \(Sym_n\) is the group of \(n\)-permutations and \(C\) is composed by the \(n\)-transpositions given by the edges of the graph \(K_{1,n-1}\), where its only vertex of degree \(n-1\) is denoted \(y_0\) and the remaining vertices are denoted \(y_a,y_b,\ldots,y_x\), where \(x\) represents the \((n-1)\)-letter of a possibly extended alphabet over \(z\) (for \(n-1=26\)) and \(y_j\in[n]\), for \(0\le j\le x\) so a typical vertex of \(ST_n\) is expressible as \(y_0y_ay_b\cdots y_x\), so its neighbors are \[y_ay_0y_b\cdots y_x,\qquad y_by_ay_0\cdots y_x,\qquad \ldots\qquad\ldots,\qquad y_xy_ay_b\cdots y_0,\] by means of the transpositions representing the edges of \(K_{1,n-1}\).
Remark 1.9. [5] Let \(1<r\in\mathbb{Z}\) and let \(n=2^r-1\). The Cayley graph \[Q_n=Cay(\mathbb{Z}^n,\{10\cdots 0,010\cdots 0,\ldots,0\cdots 01\}),\] known as the \(n\)-th Hamming cube, has its vertex set admitting a partition formed by pairwise isomorphic EDSs (perfect codes) \[\mathcal S_0,\qquad \mathcal S_1=\mathcal{S}_0+10\cdots 0,\qquad\mathcal{S}_2=\mathcal{S}_0+010\cdots 0,\qquad\ldots\qquad \ldots,\qquad \mathcal S_n=\mathcal{S}_0+0\cdots 01.\]
Here \(\mathcal S_0\), known as the \(n\)-th Hamming code, is a maximum stable set of \(V(Q_n)\) with minimum distance 3 such that \(d(v,\mathcal{S}_0)=1\), for every vertex \(v\) in the Hamming shell \(Q_n\setminus{\mathcal{S}_0}\). Moreover, \(\mathcal{S}_0\) is formed from the vertex \(0^n\) via the Steiner triple system \(STS(n)\) whose triples are formed by the coordinate directions corresponding to the linearly dependent rows of the parity check \(n\times r\)-matrix \(H_r\) whose \(\ell\)-row is the \(r\)-tuple of \(\mathbb{Z}_2^r\) associated to the binary expression of the integer \(\ell\), with enough zeros to the left to attain length \(r\), for \(\ell=1,\ldots,r\). Here, \(H_r\) has its kernel as \(\mathcal S_0\), justifying our above denomination of Hamming shell. In Section 3.1, we modify Definition 1.5 by replacing girth \(2k\) by girth \(k\) in order to present the cases of the Hamming shells.
Question 2.1. Let \(\Gamma\) be a regular graph of degree \(k\ge 3\) and girth \(2k\). Does \(\Gamma\) possess an EpGtC or EhGtC \(C\) with \(k+1\) colors? Does there exist an EpGtC or EhGtC (respectively) \(C'\) of \(\Gamma\) orthogonal to \(C\) for the graphs discussed therein?
Question 2.1 is answered in the affirmative in Subsections 2.1 and 2.2. Only the first part of Question 2.1 is answered in the affirmative for a Hamming shell of a Hamming cube considered in Subsection 2.3, as no orthogonality happens in that case.
Definition 2.2. A straight cutout of a connected toroidal graph \(\Gamma\) is a closed rectangle \(\Phi\) of \(\mathbb{R}^2\) with \(V(\Gamma)\subset\Phi\cap\mathbb{Z}^2\) and \(E(\Gamma)\) given by an hexagonal tessellation formed by 6-belts \((v,h,d,v',h',d')\) whose edges are two vertical and two horizontal unit-length segments \(v,v',h,h'\) and two main diagonals \(d,d'\) of \(1\times 1\)-squares \(v''\times h''\supset d,v'''\times h'''\supset d'\) in \(\Phi\) inside the \(2\times 2\)-square bordered by \((h,h'',v'',v',h',h''',v''',v)\) and such that identification of the left and right borders and of the top and bottom borders of \(\Phi\) yield a representation of \(\Gamma\), with the four corners of \(\Phi\) representing a sole vertex of \(\Gamma\) in \(\mathbb{Z}^2\).
Question 2.1 is answered below in the affirmative for the star transposition graph \(ST_4\) [8] represented as a straight cutout both on the left and right of Figure 1, with the edges traced thick black and the uniformly colored bright areas (green, blue, yellow) having each a central 6-cycle with darker interior (denoted a3, b3, c3, respectively). The shared straight borders between differently colored bright areas are indicated as dashed-traced segments, with their ends being the members of an efficient dominating set \(S\) given by the coinciding open neighborhoods \(N({\rm a}3)=N({\rm b}3)=N({\rm c}3)=\{3120,3102,3201,3210,3012,3021\}\), with vertex notation as in Remark 1.8. Each 6-cycle \(xj\) mentions the value \(j\in\{0,1,2,3\}\) assumed by position \(x\in\{{\rm a,b,c}\}\) in the six existing vertices of \(S\), where \(x\in\{{\rm a,b,c}\}\) indicates respectively the second, third and fourth entries of the 4-permutations \(y_0y_{\rm a}y_{\rm b}y_{\rm c}\) such that \(\{y_0,y_{\rm a},y_{\rm b},y_{\rm c}\}=\{0,1,2,3\}\).
Theorem 2.3. The star transposition graph \(ST_4\) is a \(3\)-regular graph of girth \(6\) admitting EhGtCs via the color set \(\{0,1,2,3\}\) in two vertex-fixed edge-orthogonal instances that combine to produce an EhGC of the prism graph \(ST_4\square K_2\).
Proof. Throughout the proof, each vertex \(y_0y_{\rm a}y_{\rm b}y_{\rm c}\) of \(ST_4\) is assigned color \(y_0\), which insures that \(V(ST_4)\) has a partition into efficient dominating sets [8]. Each edge of \(ST_4\) separates two faces of adjacent 6-cycles. Also, the edges of each 6-cycle form two 2-factors of three edges each. An edge coloring of \(ST_4\) is obtained by selecting in each 6-cycle \(xj\) one of its 1-factors, say \(F\), and assigning color \(j\) to the three edges of \(F\), with the outcome that all edges of \(ST_4\) get a well-defined color. More specifically, the 6-cycle \(xj\) has the edges of its remaining 1-factor \(F'\) (so \(F\cup F'=E(xj)\)), having the colors \(j_1,j_3,j_5\) of the three alternate adjacent 6-cycles \(xj_1,xj_3,xj_5\) of \(F'\), where the associated edge color sequence of \(xj\) is \((j_0,j_1,j_2,j_3,j_4,j_5)\), with \(j_0,j_2,j_4\) being the colors of the edges of \(F\). This produces an EhGtC \(C\) of \(ST_4\) depending on a specific determination of which 2-factors of the 6-cycles \(xj\) of \(ST_4\) take the roles of \(F\) and of \(F'\). Now, by exchanging the roles of the 1-factors \(F\) and \(F'\) in the argument above, a second EhGtC of \(ST_4\) is obtained, that behaves as a similar vertex coloring as that of \(C\) but that is edge-orthogonal to that of \(C\) in the sense that the roles of the 2-factors \(F\) and \(F'\) are exchanged. The resulting pair of vertex-fixed edge-orthogonal EtCs of \(ST_4\) is shown in Figure 1, where the red edge color numbers behave orthogonally while the red vertex color numbers remain fixed. The edge orthogonality property here allows to consider the prism \(ST_4\square K_2\), assign the vertex colors of \(ST_4\) to the corresponding edges of the copies \(\{v\}\square K_2\) of \(K_2\), (\(v\in V(ST_4)\)), where the end-vertices of each such edge have a common color, and take the orthogonality property to justify the claimed EhGC. ◻
Figure 2 shows a modification of Figure 1 stressing the difference between the two vertex-fixed edge-orthogonal colorings of Theorem 2.3 by means of colored triangles whose vertices are the midpoints of edges with a common color number, such that on the left of the figure these triangles are pointing down while on the right they are pointing up. The colors of these triangles are; light-gray in \(\rm a0,b0,c0\); light-green in \(\rm a1,b1,c1\); light-blue in \(\rm a2,b2,c2\); yellow in \(\rm a3,b3,c3\).
Corollary 2.4. The conclusion of Theorem 2.3 can be extended periodically to any larger straight cutout in the plane formed by a rectangular continuation of the straight cutout in Theorem 2.3, up to the whole euclidean plane.
Proof. A rectangular continuation of the two orthogonal EtCs of \(ST_4\) to any case as in the statement is sufficient to complete its proof. ◻
Total coloring of generalized Petersen graphs was addressed in [4].
A pair of orthogonal EpGtCs for the generalized Petersen graph \(GP(8,3)\) is shown in Figure 3, where, in either case, there are four of each of the following vertex-color 6-cycles: \[\begin{aligned} \label{pg83}(012013),(023021),(031032),(120123),(130132),(230231), \end{aligned} \tag{1}\] with for example a case each of color cycles \((012013)\), \((023021)\) and \((023021)\) represented in the figure with “apparent face interior” in area color yellow, blue and gray, respectively.
A pair of orthogonal EpGtC for the generalized Petersen graph \(GP(16,3)\) is shown in Figure 4, where in either case there are four of each of the following vertex-color 6-cycles: \[\begin{aligned} \label{GP163} (012312),(123023),(230130),(301201), \end{aligned} \tag{2}\] with for example a case each of these color cycles represented in the figure with “apparent face interior” in area colors yellow, blue and gray. This EpGtC generalizes as follows.
Theorem 2.5. For \(k>1\), there is a pair of orthogonal EpGtCs in \(GP(8k,3)\) with \(4k\) concatenated sequences of four vertex-color 6-cycles as in display (2).
Proof. This is a straight generalization of the argument previous to the statement of the theorem. In fact, the generalized “external” vertex-color cycle” formed by the concatenation of \(2k\) copies of the number string \((0,1,2,3)\), of the form \((0,1,2,3)^{2k}\), has its successive member vertices having respective neighbors colored \((2,3,0,1)^{2k}\) but forming a cycle of the form \((2,1,0,3)^{2k}\) by “jumping” two such neighbors in each instance, so that the vertex-color 6-cycles in display (2) are effectively constituted. No more vertex-color 6-cycles exist for \(k>1\). However, as it is shown in display (1) and illustrated in Figure 3, there are 24 vertex-color 6-cycles in \(GP(8,3)\), sixteen more than assigned by the statement for \(k>1\). More specifically, by completing the vertex-color cycles above by citing via subindices the intervening edge-colors, we rewrite those “external” and “internal” 6-cycles above as \((0_21_32_03_1)^{2k}\) and \((0_31_02_13_2)^{2k}\) for the first coloring of \(GP(8k,3)\) (represented on the left side of the figures) and as \((2_01_30_23_1)^{2k}\) and \((2_31_20_13_0)^{2k}\) for the second coloring of \(GP(8k,3)\) (represented on the right side of the figures). The 1-factor from the “external” onto the corresponding“internal” coloring in each case is formed by the edge-color period \((0_32)\), \((1_03)\), \((2_10)\), \((3_21)\) on the left and by the edge-color period \((0_12)\), \(1_23\), \(2_30\), \(3_01\) on the right. Clearly the orthogonality property holds in this case. ◻
By extension from the concept of a Hamming shell in [5], we say that given an efficient dominating set \(\Sigma\) in a graph \(G\), the complement \(G\setminus\Sigma\) of \(\Sigma\) in \(G\) is a Hamming shell of \(G\) with respect to \(\Sigma\).
Theorem 2.6. The Hamming shell of the star transposition graph \(ST_n\), (\(5\le n\in\mathbb{Z}\)), has an EtC. For \(n=5\), such tC is an EhGtC.
Proof. The vertices of \(ST_n\) are the permutations \(y_0y_ay_b\cdots y_x\) as in Remark 1.8. An edge of \(ST_n\) with one endvertex \(y_0y_ay_b\cdots y_x\) has the other endvertex obtained from \(y_0y_ay_b\cdots y_x\) by just transposing \(y_0\) with \(y_h\), for some \(h\in\{a,\ldots,x\}\). Thus, each vertex \(y_0y_ay_b\cdots y_x\) has \(n-1\) neighbors via \(n-1\) corresponding edges considered with colors \(a,b,\ldots,x\). Now, a partition into efficient dominating sets \(\mathcal S_0\), \(\mathcal S_1\), \(\ldots\), \(\mathcal S_{n-1}\) is given by defining \(\mathcal S_j\) as the subset of permutations \(y_0y_ay_b\cdots y_x\) with \(y_0= j\), for \(j\in[n]\). Then, the Hamming shell \(ST_n\setminus\mathcal S_0\) has each vertex \(v\) at distance 1 from \(\mathcal S_0\) via an edge colored with some \(h\in\{a,\ldots,x\}\). We color \(v\) with color \(h\) and this vertex color selection guarantees the existence of the claimed EtC of \(ST_n\) that becomes EhGtC for \(n=5\) since \(ST_5\setminus\mathcal S_0\) is a cubic graph with girth 6. ◻
A modification of Definition 1.5 is given in this section as Definition 3.1 and applied to Theorem 3.2 and Corollaries 3.4 and 3.5.
Definition 3.1. Let \(\Gamma\) be a connected simple \(k\)-regular graph of girth \(k\).
(a) A vertex-edge half-girth coloring, or VEhGC, of \(\Gamma\) is a tC in which the vertices of each girth cycle \(C\) are colored with \(k\) colors, each such color used twice on \(V(C)\).
(b) An efficient partial-girth total coloring, of EpGtC of \(\Gamma\) is an EtC that is also VEhGC.
Based on [5], we have the following.
Theorem 3.2. The Hamming shell \(Q_n\setminus\mathcal S_0\) has an EtC \(T\) via:
(a) the coordinate directions associated to the STS in Remark 1.9 as colors for the edges;
(b) the coordinate directions of missing edges to corresponding Hamming words as colors for the vertices, (due to the removal of \(S_0\) from \(Q_n\)).
Moreover, \(T\) is an EhGtC for \(n=7\), as \(Q_7\setminus\mathcal S_0\) is a 6-regular graph of girth 6.
Proof. An EtC \(T\) of \(Q_n\setminus\mathcal S_0\) is obtained by coloring the vertices of each \(\mathcal S_i\) with color \(i\), for \(i=1,2,3,,4,5,6,7\), and by coloring the edges of \(Q_n\setminus\mathcal S_0\) so that the color of each edge and the colors of its end-vertices form one of the triples of \(STS(n)\). ◻
Example 3.3. We have that \(STS(7)\) can be considered to consist cyclically [3] of the following successive triples: \[\begin{aligned} \label{sts}f(7)=124, f(1)=235, f(2)=346, f(3)=457, f(4)=561,cf(5)=672, f(6)=713, \end{aligned} \tag{3}\] that is the cyclic (mod 7) Steiner triple system \(STS(7)\) interpreted as triples of coordinate directions (represented by corresponding parallel 1-factors in \(Q_7\)), with \(f\) being the duality bijection from points to lines of the Fano plane. Then, \(\mathcal S_0\) is composed by the 16 7-tuples:
\[\begin{aligned} \label{hamming}\begin{array}{cccccccc} 0000000&1101000&0110100&0011010&0001101&1000110&0100011,1010001\\ 1111111&0010111&1001011&1100101&1110010&0111001&1011100,0101110\\ \end{array} \end{aligned} \tag{4}\]
Moreover, the efficient dominating sets \(\mathcal S_1\), \(\mathcal S_2\), \(\mathcal S_3\), \(\mathcal S_4\), \(\mathcal S_5\) ,\(\mathcal S_6\) and \(\mathcal S_7\), are obtained from \(\mathcal S_0\) by traversing the edges along the coordinate directions, 1, 2, 3, 4, 5, 6 and 7, respectively, by departing from the 16 vertices of \(\mathcal S_0\) in (4). By removing \(\mathcal S_0\) from \(Q_7\), the Hamming shell \(Q_7\setminus\mathcal S_0\) [3] is obtained that is a 6-regular graph whose girth is 6.
Corollary 3.4. The Hamming shell \(Q_7\setminus\mathcal S_0\) is a \(6\)-regular graph of girth \(6\) admitting EhGtCs via the color set \(\{1,2,3,4,5,6,7\}\) in two vertex-fixed edge-orthogonally instances. These instances can be combined to produce an EhGC of the prism graph \((Q_7\setminus\mathcal S_0)\square K_2\).
Proof. Adapting the proof of Theorem 2.3, a second EhGC \(T'\) of \(Q_7\setminus\mathcal S_0\) is obtained by replacing the edge colors in \(T\) by the points representing the lines of the Fano plane in (3). The final assertion of the statement is established in a similar fashion to that of the last part in Theorem 2.3. ◻
Corollary 3.5. [3] The Hamming shell \(Q_7\setminus\mathcal S_0\) is the union of two vertex-spanning self-complementary 112-vertex graphs cubic \(G_r\equiv G_b\) of girth 10 that are edge-transitive but not vertex-transitive (known as Ljubljana graph [14]). Both \(G_r,G_b\) inherit the property from \(Q_7\setminus\mathcal S_0\) of having EhGtCs from the EhGtC of \(Q_7\setminus\mathcal S_0\).
Proof. Clearly, the restriction of a total coloring on a graph to a subgraph is still a total coloring. Each edge of \(Q_7\setminus\mathcal S_0\) is of the form \((v,w)\), with the weight of \(v\) being odd and that of \(w\) even. If the color of \(v\) is \(i\) and that of \(w\) is \(j\), let us make \(vw\) be an edge of \(G_r\) if \(j-i\in\{1,2,4\}\) (mod 7) and an edge of \(G_b\), otherwise. Clearly, Definition 3.1 is satisfied both for \(G_r\) and \(G_b\). ◻