Total Coloring of Some Classes of Cayley Graphs on Non-Abelian Groups

Abstract

Total Coloring of a graph G is a type of graph coloring in which any two adjacent vertices, an edge, and its incident vertices or any two adjacent edges do not receive the same color. The minimum number of colors required for the total coloring of a graph is called the total chromatic number of the graph, denoted by ${\chi }^{″}\left(G\right)$. Mehdi Behzad and Vadim Vizing simultaneously worked on the total colorings and proposed the Total Coloring Conjecture (TCC). The conjecture states that the maximum number of colors required in a total coloring is $\Delta \left(G\right)+2$, where $\Delta \left(G\right)$ is the maximum degree of the graph G. Graphs derived from the symmetric groups are robust graph structures used in interconnection networks and distributed computing. The TCC is still open for the circulant graphs. In this paper, we derive the upper bounds for ${\chi }^{″}\left(G\right)$ of some classes of Cayley graphs on non-abelian groups, typically Cayley graphs on the symmetric groups and dihedral groups. We also obtain the upper bounds of the total chromatic number of complements of Kneser graphs.

1. Introduction

Let G be a graph with the set of vertices $V\left(G\right)$ and the set of edges $E\left(G\right)$, respectively. Any two adjacent or incident elements are assigned different colors in a total coloring of a graph. The total chromatic number of the graph G, denoted by ${\chi }^{″}\left(G\right)$, is the minimum number of colors needed in a total coloring. It is easy to see that ${\chi }^{″}\left(G\right)\ge \Delta \left(G\right)+1$, where $\Delta \left(G\right)$ is the maximum degree of G. Mehdi Behzad ([1]) and Vadim Vizing ([2]) independently conjectured that for every graph G, ${\chi }^{″}\left(G\right)\le \Delta \left(G\right)+2$, which is called the Total Coloring Conjecture (TCC). The graphs that have ${\chi }^{″}\left(G\right)=\Delta \left(G\right)+1$ colors are called type I, and those with ${\chi }^{″}\left(G\right)=\Delta \left(G\right)+2$ are called type II. The TCC is close to 50 years old and has not been completely proven yet. However, it has been shown that the decision problem of determining the total chromatic number, given an upper bound, is NP-complete even for cubic bipartite graphs [3,4]. Nevertheless, a lot of progress has been made toward proving the TCC. It has been proved that complete graphs, bipartite graphs, and complete multi-partite graphs satisfy the TCC. The total coloring conjecture has also been verified for several other classes of graphs. Some good survey articles and books listing the basic techniques and other results on total coloring are Yap [5], Borodin, [6], and Geetha et al. [7].

A weakening of the TCC is a weak TCC, which conjectures that the total chromatic number is bounded above by $\Delta \left(G\right)+3$ ([8]).

A similar scenario exists in the edge coloring of graphs. According to Vizing’s Theorem, only $\Delta \left(G\right)+1$ suffices for the proper edge coloring of graphs. The TCC was inspired by Vizing’s Theorem for edge coloring. A graph G is said to be class I if it requires $\Delta \left(G\right)$ colors for its edge coloring.

A Cayley graph is a graph defined on a group H with respect to a symmetric generating set $S\subset H$. The vertices of a Cayley graph are the elements of the group, and two vertices x and y in the graph are adjacent if and only if $x=ys$ for some $s\in S$. The definition of a symmetric generating set is that if $s\in S$, then $s^{-1}\in S$. We also assume that the generating set S does not contain the identity element of the group H. We denote the Cayley graph of a group H to be $C(H,S)$, where S is the symmetric generating set of the group and the graph.

2. Cayley Graphs of Permutation Groups with Transposition Generators

The symmetric group of order n, denoted by $S_n$, is the group that consists of all bijective functions from a set of cardinality n to itself, with the composition of functions as the group operation. The elements of the symmetric group are written in the parenthesis (bracket) notation, with a resemblance to that used in SageMath software. The elements that have exactly two elements in their bracket notations are called transpositions. The set of all transpositions of $S_n$ generates the whole group. A minimal generating set for the symmetric group of order n contains the transpositions of the form $(1,2),(1,3),\dots ,(1,n)$ ([9]). For $j\in \{1,2,\dots ,n\}$, it is easy to see that the set $T_j\left(n\right)=\{(i,j):i,j\in \{1,2,\dots ,n\},i\ne j\}$ is also a minimal generating set of $S_n$. Similarly, the set of all transpositions in a symmetric group of order n is denoted by $T\left(n\right)$. Two elements $a,b$ of the symmetric group $S_n$ are similar with respect to elements $c,d$ if we have $a=cb{d}^{-1}$. If the elements $a,b$ are similar with respect to the same element, then they are conjugate.

We know that all bipartite graphs satisfy the TCC ([5]). In addition, we know that $C(S_n,S)$ with S having only transpositions are bipartite graphs. Hence, it satisfies the TCC. In Theorem 1, we prove that the ${\chi }^{″}\left(C(S_n,S)\right)=\Delta \left(C(S_n,S)\right)+1$ for some S.

Theorem 1.

Let X be any generating set of $S_{n-1}$ that consists only of transpositions with a subset of $T_j(n-1)$ for at least one j. If the graph $C(S_{n-1},X)$ is of type I, then the graph $C(S_n,Y_n)$ is also of type I for all n, where $Y_n=T_j\left(n\right)\cup X$.

Proof. 

We first prove that the vertices of all the graphs $C(S_n,Y_n)$ can be colored in the same manner as in a type I total coloring of the graph $C(S_{n-1},X)$.

Let us assume that we have divided the vertices of the graph $C(S_{n-1},X)$ as in a type I total coloring of $C(S_{n-1},X)$. Let the independent sets be labeled $I_1,I_2,\dots ,I_k$. In addition, let the left cosets of $S_{n-1}$ with $S_n$ be labelled $S_{n-1},(1,n)S_{n-1},(2,n)S_{n-1},$$(3,n)S_{n-1},\dots ,(n-1,n)S_{n-1}$. We now divide the vertices of each of the n cosets identical to the division of the vertices of $S_{n-1}$ and label them correspondingly, $I_{11},I_{12},\dots ,I_{1k}$ (corresponding to $S_{n-1}$), $I_{21},I_{22},\dots ,I_{2k}$ (corresponding to $(1,n)S_{n-1}$), and so on, up to $I_{n1},I_{n2},\dots ,I_{nk}$ (corresponding to $(n-1,n)S_{n-1}$. To form independent sets of $C(S_n,Y_n)$, we concatenate the independent sets of all cosets by shifting the independent sets of all the cosets, except for the first coset (principal coset corresponding to $S_{n-1}$) one position down (modulo k). This means that the independent sets of elements of $C(S_n,Y_n)$ are $[I_{11},I_{2k},\dots ,I_{nk}],[I_{12},I_{21},\dots ,I_{n1}],\dots ,[I_{1n},I_{2(k-1)},\dots ,I_{n(k-1)}]$.

The concatenation so formed would form independent sets of $C(S_n,Y_n)$, as shifting one position downward would omit the adjacency formed due to the generating element $(j,n)$. This is because no element of the symmetric group $S_{n-1}$ is conjugate to any other element with respect to two transpositions of the form $(i,n),(j,n)$, where $i,j$ are any of the integers $1,2,3,\dots ,n$.

To see this, if we have adjacencies between an element $g_1$ of one of the independent sets of $I_{1s},s=1,2,\dots ,k$ (corresponding to the principal coset $S_{n-1}$) and any other element $(i,n)g_2$ in the same independent set corresponding to any other coset ($I_{sp},s=2,3,\dots ,n;p=\{1,2,\dots ,k$}), we should have $g_1(j,n)=(i,n)g_2$, where $i\in \{1,2,3,\dots ,n-1\}$. This implies, by right multiplication, that $g_1=(i,n)g_2(j,n)$. Then, if $g_1$ takes an element a, $a\ne i\in \{1,2,\dots ,n-1\}$, to $b\in \{1,2,\dots ,n-1\}$, $g_2$ also should take a to b, for $(i,n)$ fixes the element a. As for i, both $g_1$ and $g_2$ must take i to j by similar reasoning. Thus, $g_1=g_2$. However, in our concatenation of independent sets, $g_1\ne g_2$; by shifting one independent set of vertices downward, we can rule out this possibility. This gives us independence of the principal coset $I_{1s}$ (corresponding to $\left(S_{n-1}\right)$) from the rest of the cosets.

Similarly, let us have $g_2=g_{1}m,m\in S_{n-1}$. To see the independence among the elements in the same independent sets of $I_{2s}$ up to $I_{ns},s=1,2,\dots ,k$ (corresponding to non-principal cosets), we can see that if there was an adjacency between one element $(i,n)g_1$ and another element $(k,n)g_2$ in the same independent set, we would have $(i,n)g_1(j,n)=(k,n)g_2\Rightarrow g_1=(i,n)(k,n)g_2(j,n)\Rightarrow (k,n)(i,n)=g_{1}m(j,n)g_1^{-1}$, provided $i\ne k$ as before. Now, we know that two elements in the symmetric group $S_n$ are conjugate if and only if they have the same cycle structure and transposition decomposition. Here, as $(k,n)(i,n)$ is a 3-cycle having two transpositions in their product structure, we can say that m must either be a 4-cycle with one transposition factor being $(j,n)$ or must be a simple transposition having one symbol in common with $(j,n)$. Since m fixes n, we must have $m=(a,j)$, where $a=\{1,2,\dots ,n-1\}-\left\{j\right\}$. However, this violates the fact that $g_1,g_2$ are elements in the same independent set of $C(S_{n-1},Y_{n-1})$. Therefore, we can say that we can divide all the vertices of $C(S_n,Y_n)$ into the same number of sets as the vertices of $C(S_{n-1},X)$.

Now, we give the edge coloring of $C(S_n,Y_n)$ in the following way. Let the maximum degree of $C(S_{n-1},X)$ be ${\Delta }_X$ and that of $C(S_n,Y_n)$ be ${\Delta }_{Y_n}$. We can color all the corresponding edges of the cosets of $C(S_{n-1},X)$ in $C(S_n,Y_n)$ in a similar way, except that the edges induced by the sets $I_{2s}$ up to $I_{ns},s=1,2,\dots ,k$ (corresponding to non-principal cosets) receive a shift in coloring. The edges that were colored with the first color in the induced graph formed by the sets $I_{1s},s=1,2,\cdots ,k$ (corresponding to the principal coset) will receive the second color, the edges colored with the second color in the principal coset will receive the third color in the other cosets, and so on. For the remaining edges connecting the different cosets, we use the class I nature of the graph $C(S_n,Y_n)$ to give a coloring. The remaining edges can be factorized into 1-factors, one for each transposition in $Y_n-X$. Since the graph $C(S_4,X)$ is of type I, the number of colors required to totally color the graph $C(S_n,Y_n)$ is ${\Delta }_X+1+({\Delta }_{Y_n}-{\Delta }_X)={\Delta }_{Y_n}+1$. Hence, the graph $C(S_n,Y_n)$ is also of type I. □

Corollary 1.

The graph $G=C(S_n,T_1\left(n\right)),n\ge 3$ is of type I. For $n=2$, $C(S_2,T_1\left(2\right))$ is the single edge $K_2$, which is trivially seen to be of type II.

Proof. 

We note that $C(S_3,T_1\left(3\right))$ is a 6-cycle, which is well known to be of type I (from [5]). Having $j=1$ in the notation of the previous theorem gives us the set $X=T_m\left(3\right)=T_1\left(3\right)$. We obtain the desired result using the previous theorem by putting $j=1$ to the graph $C(S_3,X)$. □

Corollary 2.

The graph $G=C(S_n,S),n\ge 4$ with $S=T\left(n\right)-U$, where U is any combination of two transpositions from $Z=\left\{\right(1,2),(1,3),(1,4),(2,3),(2,4),(3,4\left)\right\}$, is of type I.

Proof. 

We computed the total chromatic number of all the graphs $C(S_4,X)$ with $X=T\left(4\right)-U$ using the SageMath software, which output a value of 5; in other words, they were of type I. The code is given in Appendix A.1. Using the previous theorem by putting $j=1$ or $j=2$ to the graph $C(S_4,S)$, we obtain the desired result. □

Corollary 3.

The graph $G=C(S_n,T\left(n\right))$ for $n\ge 4$ is of type I.

Proof. 

The algorithm used in the program of the previous corollary used a greedy-like algorithm to compute the total chromatic number. Instead, we used an algorithm based on mixed-integer linear programming (MILP), which was faster than the usual approach. The code is given in Appendix A.2. Again, using the above theorem with $j=1,2,3,4$ with $X=T\left(4\right)$ for the base graph $C(S_4,T\left(4\right))$ gives us the desired result. □

We note that in the last two corollaries, the condition $n\ge 4$ is necessary, otherwise, we have the graph $C(S_3,T\left(3\right))$ being a complete regular bipartite graph, which is of type II.

Example 1.

By using the 3-total coloring of $C(S_3,T_1\left(3\right))$, we can obtain the 4-total coloring of $C(S_4,T_1\left(4\right))$, in which the vertices or elements of $S_4$ are divided into independent sets as

 

$[e,(2,3),(1,4,3),(1,4,3,2),(1,3\left)\right(2,4),(1,3,2,4),(1,3,4),(1,3,4,2\left)\right]$,

 

$\left[\right(1,2),(1,3,2),(1,4),(1,4\left)\right(2,3),(2,4),(2,4,3),(3,4),(2,3,4\left)\right]$,

 

$\left[\right(1,3),(1,2,3),(1,4,2),(1,4,2,3),(1,2,4),(1,2,4,3),(1,2\left)\right(3,4),(1,2,3,4\left)\right]$.

 

We use the algorithm described above to give a 3 coloring of the elements of $S_5$, which is achieved by dividing the elements into three independent sets as

 

$$\begin{gathered} [e,(2,3),(1,4,3),(1,4,3,2),(1,3\left)\right(2,4), \\ (1,3,2,4),(1,3,4),(1,3,4,2),(1,5,3),(1,5,2,3),(1,5,4,2),(1,5,4,2,3), \\ (1,5,2,4),(1,5,2,4,3),(1,5,2\left)\right(3,4),(1,5,2,3,4),(2,5\left)\right(1,3),(1,2,5,3), \\ (1,4,2,5),(1,4,2,5,3),(1,2,5,4),(1,2,5,4,3),(1,2,5\left)\right(3,4),(1,2,5,3,4), \\ (1,3,5),(1,2,3,5),(3,5\left)\right(1,4,2),(1,4,2,3,5),(3,5\left)\right(1,2,4),(1,2,4,3,5), \\ (1,2\left)\right(3,5,4),(1,2,3,5,4),(4,5\left)\right(1,3),(4,5\left)\right(1,2,3),(1,4,5,2),(1,4,5,2,3), \\ (1,2,4,5),(1,2,4,5,3),(1,2\left)\right(3,4,5),(1,2,3,4,5\left)\right] \end{gathered}$$

 

$$\begin{gathered} \left[\right(1,2),(1,3,2),(1,4),(1,4\left)\right(2,3),(2,4),(2,4,3), \\ (3,4),(2,3,4),(1,5,2),(1,5,3,2),(1,5,4),(1,5,4\left)\right(2,3), \\ (1,5\left)\right(2,4),(1,5\left)\right(2,4,3),(1,5\left)\right(3,4),(1,5\left)\right(2,3,4),(1,2,5),(1,3,2,5), \\ (2,5\left)\right(1,4),(1,4\left)\right(2,5,3),(2,5,4),(2,5,4,3),(2,5\left)\right(3,4),(2,5,3,4), \\ (3,5\left)\right(1,2),(1,3,5,2),(3,5\left)\right(1,4),(1,4\left)\right(2,3,5),(3,5\left)\right(2,4),(2,4,3,5), \\ (3,5,4),(2,3,5,4),(4,5\left)\right(1,2),(4,5\left)\right(1,3,2),(1,4,5),(1,4,5\left)\right(2,3), \\ (2,4,5),(2,4,5,3),(3,4,5),(2,3,4,5\left)\right] \end{gathered}$$

 

$$\begin{gathered} \left[\right(1,3),(1,2,3),(1,4,2),(1,4,2,3),(1,2,4),(1,2,4,3), \\ (1,2\left)\right(3,4),(1,2,3,4),(1,5,2),(1,5,3,2),(1,5,4),(1,5,4\left)\right(2,3), \\ (1,5\left)\right(2,4),(1,5\left)\right(2,4,3),(1,5\left)\right(3,4),(1,5\left)\right(2,3,4),(1,2,5),(1,3,2,5), \\ (2,5\left)\right(1,4),(1,4\left)\right(2,5,3),(2,5,4),(2,5,4,3),(2,5\left)\right(3,4),(2,5,3,4), \\ (3,5\left)\right(1,2),(1,3,5,2),(3,5\left)\right(1,4),(1,4\left)\right(2,3,5),(3,5\left)\right(2,4),(2,4,3,5), \\ (3,5,4),(2,3,5,4),(4,5\left)\right(1,2),(4,5\left)\right(1,3,2),(1,4,5),(1,4,5\left)\right(2,3), \\ (2,4,5),(2,4,5,3),(3,4,5),(2,3,4,5\left)\right] \end{gathered}$$

 

Now, the edge coloring is performed as described in the algorithm, that is, the edges of the induced graph corresponding to $S_4$ are given the usual type I coloring (the total coloring is of type I, as the induced graph formed by any two independent sets is a regular bipartite graph). The corresponding edges of the induced subgraphs of cosets $(1,5)S_4,(2,5)S_4,(3,5)S_4,(4,5)S_4$, which are isomorphic, are also given the same color while concatenating the independent edges; the edges of the induced subgraphs corresponding to the non-principal cosets are shifted one position down to that of the principal coset edges.

The next theorem is a direct consequence of the main theorem of [10].

Theorem 2.

The graph $G=C(A_n,S)$ with $S=\left\{\right(1,2,3),(1,2,4),\dots ,(1,2,n),(1,n,2),$ $\dots ,(1,4,2),(1,3,2)\}$ is a class I.

Proof. 

We use the information in [10] to partition the edges of G to $n-2$ edge-disjoint Hamiltonian cycles. Then, we bi-color each disjoint Hamiltonian cycle to obtain the class 1 coloring of the edges of G. □

The above theorem, combined with the fact that the graphs $C(A_n,S)$ for $n=3,4,5,6$ are of type I, leads us to conjecture that the graphs $C(A_n,S)$ for all n are of type I.

3. Cayley Graphs on Dihedral Groups

The dihedral groups, denoted by $D_{2n}$, are the groups that consist of symmetries of an n-gon. The minimal generators of dihedral groups in the following are $\{r,s\}$, where r is a reflection element having order 2 and s is a rotation element having order n with the usual group defining the relation ${\left(rs\right)}^2=e$. We see that the rotation element generates the cyclic group of order n (${\mathbb{Z}}_n)$, and its elements are denoted by $\{0,1,2,\dots ,n-1\}$.

As 1 is always a generating element for the cyclic group ${\mathbb{Z}}_n$, let us assume $s=1$. Then, we could write the elements $r{s}^a$ as $ra$. We use this notation in the following theorems. Note that $r0$ is the same as r.

Theorem 3.

If n is even and $G=C(D_{2n},S)$ with $S=\{ri,1,2,\dots ,k,n-k,\dots ,n-2,n-1\},i\in \{0,1,2,\dots ,n-1\}$, then G satisfies the TCC.

Proof. 

We see that G has two induced subgraphs (one formed by the vertices $\{0,1,2,\dots ,n-1\}$ and the other formed by the vertices $\{r,r1,r2,\dots ,r(n-1\left)\right\}$) of order n corresponding to the generating subset $\{1,2,\dots ,k,n-k,n-k-1,\dots ,n-1\}$, which correspond to the power of cycle $C_n^k$. Hence, the graph G can be seen as the Cartesian product of $K_2$ with $C_n^k$. Using the results of Campos and de Mello [11], we know that $C_n^k$ satisfies the TCC. Hence, by the fact that the Cartesian product of a graph X with a graph Y satisfies the TCC, $X\square Y$ also satisfies the TCC (Theorem 1 of [12]) and we obtain the results immediately. □

Example 2.

We take $C(D_{72},S)$ with the generating set $S=\{1,2,3,4,32,33,34,35,r\}$. Then, we have the graph induced by the vertices $0,1,\dots ,n-1$ is the power of cycle $C_{36}^4$, which satisfies the TCC. This total coloring of $C_{36}^4$ can be extended to color all vertices of $C(D_{72},S)$ using the above method.

A generalization of the last theorem is the following corollary, which is an immediate consequence.

Corollary 4.

Suppose that $T=T_1\cup T_2$, where $T_1\subset \{0,1,2,\dots ,n-1\}$, and H is the circulant graph of order n with generating set $T_1$. If H has ${\chi }^{″}\left(H\right)=\left|T_1\right|+2$ and $T_2=\left\{ri\right\}$, where $i\in \{0,1,2,\dots ,n-1\}$, then $C(D_{2n},T)$ satisfies the TCC.

Proof. 

Here, the graph could be seen as the Cartesian product of $C({\mathbb{Z}}_n,T_1)$ with $K_2$. Since $C({\mathbb{Z}}_n,T_1)$ is seen to satisfy the TCC by the conditions given in Theorem 1 of [12] on the total coloring of the Cartesian products of graphs, the results follow immediately. □

Note that in the above theorem and corollary, if the graph $C_n^k$ or $C({\mathbb{Z}}_{⋉},T_1)$ were of type I, then G will also be of type I, again using Corollary 2 of [12]. Some classes of graphs, where $C_n^k$ are of type I, are highlighted in [13,14,15,16].

Example 3.

Consider the group $D_{36}$ with generating set $\{1,3,5,7,9,11,13,15,17,r2\}$. Then, we have the graph induced by the vertices $0,1,\dots ,n-1$ and $r,r1,r2,\dots ,r(n-1)$ as a unitary Cayley graph on 18 vertices, which is known to satisfy the TCC from [15], which can be extended to color all vertices of the Cayley graph on $D_{36}$.

Theorem 4.

If n is even, then $C(D_{2n},S)$ with $S=\{r,r(n-1),\dots ,r(n-x),1,2,\dots ,k,n-k,\dots ,n-2,n-1\}$ and $x<k$ satisfies the TCC.

Proof. 

We see that G has two induced subgraphs of order n corresponding to the generating subset $\{1,2,\dots ,k,n-k,n-k-1,\dots ,n-1\}$, which is the power of cycle $C_n^k$. We color the first copy of the power of cycle (corresponding to the vertices $\{0,1,2,\dots ,n-1\})$ according to the coloring described in [11] to give a total coloring with at most $2k+2$ colors. The second copy of $C_n^k$ (corresponding to the vertices $\{r,1r,\dots ,(n-1\left)r\right\}$) is given a shifted coloring, that is, we give the vertex r the color given to vertex 1, the vertex $1r$ gets the color given to vertex 2, and so on with the last vertex $(n-1)r$ receiving the color given to vertex 0. Since $x<k$, this shifted coloring ensures that the edges connecting one copy of $C_n^k$ with the other do not clash vertices of the same color. This is because any $k+1$ consecutive vertices form a clique in $C_n^k$, and since the generating set consists of the elements $r,r(n-1),r(n-2),\dots ,r(n-x)$, the downward shifted coloring will give different colors to adjacent vertices by the total coloring given to the first copy of $C_n^k$. The edges of the second copy of $C_n^k$ are colored in the same way as the first copy, except that the downward shift of vertices means that the corresponding edges that were colored with the second color in the first copy would receive the first color in the second copy, the corresponding edges that were colored with the third color in the first copy would receive the second color in the second copy, and so on. The remaining edges, which are the edges connecting one copy of $C_n^k$ with the other, can be easily one-factorized, which can clearly be seen, as each of the generating elements $r,r(n-1),r(n-2),\dots ,r(n-x)$ gives a perfect matching; or we could invoke Corollary 2.2.3 of [17]. These edges could be given one color corresponding to each extra generating element (one for each of $r,r(n-1),\dots ,r(n-x)$, thus proving that the graph G also satisfies the TCC. □

Theorem 5.

The graph $C(D_{2n},T)$ satisfies the TCC if the following conditions hold:

1. 

$T=T_1\cup T_2$ with $T_1\subset \{0,1,2,\dots ,n-1\}$.

2. 

The circulant graph G of order n with generating set $T_1$ satisfies the TCC.

3. 

In a total coloring of G with at most $\Delta \left(G\right)+2$ colors, each total independent set has at most k vertices, and any pair of vertices $x,y$ in an independent set satisfy $x-y=md,m\le k-1$.

4. 

$T_2=\overline{T_1}-\{0,ri,r(i-d),\dots ,r(i-kd+d)\}$.

Proof. 

We first color the vertices $\{0,1,2,\dots ,n-1\}$ as in a $|T_1|+2$ total coloring of G so that the difference between any pair of vertices is equal to $md,m\le k-1$. We can extend this vertex coloring to the vertices of $C(D_{2n},T)$ by forming orbits of the former independent sets (right cosets) with the element $ri$. This is because, $T_2$ excludes the elements $\{ri,r(i-d),\dots ,r(i-kd+d\left)\right\}$, whereby the adjacencies of the elements of G are excluded.

For the edge coloring of $C(D_{2n},T)$, we can bifurcate the edges into two parts—one among the induced graphs formed by the vertices $\{0,1,2,\dots ,n-1\}$ and $\{r,r1,r2,\dots ,r(n-1\}$ (which are isomorphic), and another between the two induced subgraphs. For coloring the edges in the induced graphs formed by vertices $\{0,1,2,\dots ,n-1\}$ and $\{r,r1,r2,\dots ,r(n-1\left)\right\}$, we use the same edge coloring used for the edges of G. For the edges between these two induced subgraphs, we give one color for each of the edges (matchings) generated by an element in $T_2$. Therefore, we require at most $|T_1|+|T_2|+2=|T|+2$ colors to totally color the graph, which therefore verifies the TCC. □

Example 4.

If $n=8k+4$ and the graph to be colored is $C(D_{2n},T)$ with $T=T_1\cup T_2$ and $T_1=\{1,2,\dots ,k,n-k,\dots n-2,n-1\}$, $T_2=D_{2n}-T_1-\{0,r(2k+1),r(4k+2),r(6k+3),r(8k+4)\}$, we see that $G=C({\mathbb{Z}}_n,T_1)$ is the power of cycle graph $C_{8k+4}^k$, which, has ${\chi }^{″}\left(G\right)=2k+1$ colors. In addition, the difference between the pairs of vertices in any independent set of vertices is equal to a multiple of $2k+1$ by the coloring used in ([15], Theorem 2.6). In addition, each independent set of vertices in the former total coloring has exactly four vertices. Using the above theorem, this total coloring of G can be extended to $C(D_{2n},T)$, in which we can color the graph using $\left|T\right|+1=2n-2k-2$ colors, which implies that $C(D_{2n},T)$ is of type I.

4. Complement of Kneser Graphs

We denote the Kneser graphs by $K(n,k)$. These graphs consist of $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ vertices, which correspond to the k-element subsets of an n-element set. Two vertices in $K(n,k)$ are adjacent if those vertices correspond to disjoint sets.

Hypergraphs are generalizations of simple graphs. They consist of n vertices with hyperedges corresponding to some $k_i$-element subsets of an n-element set where $i\in \{1,2,\dots ,n\}$. A hypergraph is said to be k-uniform if the hyperedges all have the same cardinality, that is, $k_i=k$, which is a constant. Furthermore, if all the k-element sets are hyperedges, then the hypergraph is said to be k-complete, denoted by $H(n,k)$. It is then readily seen that the line graph (a graph whose vertices are the hyperedges, and two vertices are adjacent if the hyperedges are incident at a vertex in $H(n,k)$) of a complete hypergraph corresponds to the complement of $K(n,k)$. In particular, the complement of the line graph of the complete graph $K_5$ is the Petersen graph. An odd graph $O_n$ is the Kneser graph $K(2n-1,n-1)$. The TCC was proved for the odd graphs $O_n$ [15].

Theorem 6.

If n is even and $k\mid n$, then the complement of the Kneser graph $K(n,k)$, $G=\overline{K(n,k)}$ satisfies the weak TCC.

Proof. 

Using Baranayai’s theorem (see [18]), we can factorize the hyperedges of $H(n,k)$ evenly into $\frac{\left(\genfrac{}{}{0pt}{}{n}{k}\right)}{\frac{n}{k}}=\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$ classes. This, in turn, means that we can divide the vertices of $\overline{K(n,k)}$ into $\frac{n}{k}$ disjoint cliques having $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$ vertices, which gives a $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$ coloring of the vertices. For the edge coloring of G, we use the edge coloring in a total coloring of the complete graph of order $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$. We first color the vertices and edges of each clique of order $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$ using the total coloring of a clique of order $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$. This gives a partial $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$ or $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)+1$-total coloring of $\overline{K(n,k)}$. We can then extend it to G by adding extra colors to color the connecting edges between the cliques. Since at most $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)+1$ colors are required to color all the disjoint cliques, therefore, according to Vizing’s Theorem, we require at most $\left(\genfrac{}{}{0pt}{}{n-k}{k}\right)-\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)+2$ colors to color the connecting edges joining the cliques. Thus, the total number of colors required is at most $\left(\genfrac{}{}{0pt}{}{n-k}{k}\right)-\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)+2+\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)+1=\left(\genfrac{}{}{0pt}{}{n-k}{k}\right)+3=\Delta \left(\overline{K(n,k)}\right)+3$ colors. Hence, $\overline{K(n,k)}$ satisfies the weak TCC. □

Corollary 5.

If n is even and $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$ is odd, then $\overline{K(n,k)}$ satisfies the TCC. In addition, if the subgraph consisting of the remaining edges (induced by the connecting edges between the cliques of order $\frac{n}{k}$) is of class I, then the graph $\overline{K(n,k)}$ is of type I.

Proof. 

The proof is a direct consequence of the former theorem, as we know that the clique of odd order $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$ has ${\chi }^{″}\left(G\right)=\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$. □