Total Coloring of Some Graph Operations

Abstract

The total chromatic number $\chi _T (G)$ of G is the least positive integer k for which G admits a k-total coloring. Clearly, $\chi _T (G) \ge \varDelta (G)+1$. A long standing Total Coloring Conjecture (TCC) asserts that every graph G has $\chi _T(G) \le \varDelta (G)+2$. If $\chi _T (G) = \varDelta (G)+1$, then G is a type-1 graph and if $\chi _T (G) = \varDelta (G)+2$, then G is a type-2 graph. Weak TCC states that any simple graph G has $\chi _T(G)\le \varDelta (G)+3$. In this paper, we give an upper bound for the total chromatic number of the join $G\vee H$ of graphs G and H. Also, we verify that if G satisfies TCC, then $G\vee G$ satisfies TCC and the join of two type-1 graphs having the same order satisfies TCC. We show that $G\vee H$ satisfies weak TCC under certain constrains. Moreover, we show that the join of any two graphs G and H of same order satisfies weak TCC if both G and H are satisfying TCC. Also, we prove that if G and H are any two k-regular graphs with same odd order, then $G\vee H$ is not type-1. In addition, we verify that the join of any two cycles satisfies TCC. We give an upper bound for the total chromatic number of generalized join of graphs and as a result we obtain an upper bound for the total chromatic number of the lexicographic product $G\circ H$ of G and H in terms of the maximum degrees of G and H if H satisfies TCC. Also, we show that the lexicographic product of a graph with compliment of complete graphs satisfies weak TCC. In particular, when the graph is Type-1 then this lexicographic product will satisfy TCC.

1 Introduction

All graphs considered here are finite, simple and undirected. Let $G = (V(G),E(G))$ be a graph with vertex set V(G) and edge set E(G). For $v \in V(G),$ let $N_G(v)$ denote the open neighborhood of v and $N_G[v]$ denote the closed neighborhood of v. $\varDelta (G)$ denote the maximum degree of G. For any A which is a subset of V(G), $\langle A\rangle$ denotes the subgraph induced by A. Graph coloring is the process of assigning colors to the elements of a graph. Graph coloring has various practical applications also. There are different kinds of graph colorings like, vertex coloring, edge coloring, total coloring etc. If the coloring is for the vertices only, then it is said to be vertex coloring or simply coloring. If the coloring is for edges only, then it is said to be the edge coloring. Total coloring is the coloring in which we assign colors to both the vertices and edges of a graph and it is said to be proper if no two adjacent or incident elements are receiving the same color. A k-total coloring is the total coloring in which we are using k colors. Total chromatic number of a graph G denoted as $\chi _T(G)$ is the minimum number of colors required for coloring the vertices and edges of the graph properly (Similarly we can define chromatic number ($\chi (G)$) and chromatic index number ($\chi '(G)$) corresponding to the vertex and edge coloring, respectively). Graphs with $\chi '(G)=\varDelta (G)$ are called class-1 and graphs with $\chi '(G)=\varDelta (G)+1$ are called class-2. Also, graphs with $\chi _T(G)=\varDelta (G)+1$ are called type-1 and graphs with $\chi _T(G)=\varDelta (G)+2$ are called type-2.

In the year 1953 Behzad [1] conjectured that $\varDelta (G)+2$ is an upper bound for $\chi _T(G)$. It is known as the Total Coloring Conjecture (TCC), which is one among the classic open problems in graph theory. TCC is studied widely by various mathematicians. During $1980's$, S$\acute{a}$nchez-Arroyo [15] proved that deciding whether a graph is type-1 or not is NP-complete and also the total coloring of a complete bipartite graph is NP-hard. Moreover, McDiarmid and S$\acute{a}$nchez-Arroyo [11] proved that determining the total chromatic number is NP-hard even for r-regular bipartite graphs, for each fixed $r\ge 3$. It can be easily seen that TCC is true for the complete graphs [2], cycles and bipartite graphs.

In case of planar graphs, so many results related to TCC have been done and are mainly based on the maximum degree and the girth constraints. For planar graphs with maximum degree at most 5, TCC was verified by A. V. Kostochka [7] during the late 90’s. Yap [21] verified it for planar graphs with maximum degree at least 8 and Kowalik et. al. [8] proved that for any planar graph with maximum degree at least 9 is type-1. For the planar graphs with maximum degree 6 and 7, TCC was verified under certain conditions. For the non-planar case, TCC is verified for so many classes of graphs. TCC for the cartesian product of two graphs is verified for many cases [5], and still there are cases for which it is not verified. But regarding the other graph products only a few results are proved on TCC yet [3, 20]. Geetha et al. [4] have produced an excellent survey on total coloring, which is a valuable source of information in the state of art.

Even though many well-known researchers from different parts of the world have studied TCC for over 60 years, it remains open till now. So it make sense for the current researchers to go for some relaxed version of TCC which is known as the Weak TCC. Before defining the weak TCC we define some more weaker version of TCC called the k-TCC which was introduced by Manu Basavaraju et al. in [10].

k-Total coloring Conjecture (k-TCC).

For any graph G, $\chi _T(G)\le \varDelta (G)+k$, for some fixed positive integer $k\ge 2$.

The 2-TCC is nothing but the original TCC and 3-TCC is known as the weak TCC. Molloy and Reed [13] showed a probabilistic approach to prove that for a sufficiently large $\varDelta ,~ \chi _T(G)\le \varDelta (G)+C$, where $C=10^{26}$.

Let G be a graph with n vertices and $H_1,H_2, \ldots , H_n$ be a collection of graphs. The G-generalized join of $H_1,H_2,\ldots , H_n$, denoted by $G[H_1,H_2,\ldots , H_n]$, is the graph $G'$ with vertex set $V(G')= \displaystyle \bigcup _{i=1}^{n}$ $V(H_i)$ and edge set $E(G')=\Big (\displaystyle \bigcup _{i=1}^{n} E(H_i)\Big ) \cup \Big (\bigcup _{ij\in E(G)} \{ xy|x\in V(H_i), y\in V(H_j)\}\Big )$.

If $H_i \cong H$ for $1\le i \le n$, then $G[H,H,\ldots , H]$ is the standard lexicographic product of G and H and it is denoted as $G\circ H$. If $G=K_2$, then $K_2[H_1,H_2]$ is the well known join of graphs $H_1$ and $H_2$ and it is denoted by $H_1\vee H_2$.

A complement reducible graph (also called a co-graph) is defined recursively as follows:

• i) A graph on a single vertex is a complement reducible graph.

• ii) If $G_1,G_2,\ldots , G_k$ are complement reducible graphs, then so is their union $G_1\cup G_2\cup \dots \cup G_k$.

• iii) If G is a complement reducible graph, then so is its complement.

The co-graphs have arisen in many disparate areas of mathematics and have been independently rediscovered by various researchers. The verification of TCC for the join of two graphs will automatically shows that the co-graphs also satisfies TCC. But verifying TCC even for the join of some simple classes of graphs will pause many difficulties, which can be seen from some proofs that we have given in this paper. In our journey to verify TCC for co-graphs, we find some results that contribute more power to the validity of TCC in general but, TCC for the join of two arbitrary graphs remains still open.

Some works that have been done regarding the verification of TCC for the join of certain classes of graphs are as follows : Seoud et al. [16, 17] calculated the total chromatic number of the join of two paths. Guanggrong Li and Limin Zhang [9] proved that the join of a complete in-equipartite graph and a path is type-1. In their proof the difficulty in proving TCC for the join of such graphs (that is $K_{n_1,n_2}$ for $n_1\ne n_2$ and $P_m$) is easily visible as there arises various sub cases for a single proof (see [9]). Further Wang et al. [20] proved the equality of the vertex distinguishing total chromatic number and the total chromatic number of the join of a path with itself and a cycle with itself.

In [19], R. Vignesh et al. proved the validity of TCC for the join of a graph satisfying TCC with itself. But we found that the existence of a proper edge coloring that is just mentioned in the proof without any proper explanation is not always mandatory. Hence in order to overcome that here we give a rigorous proof using the coloring technique explained in the Lemma given in the second section.

Even though we do not have a proof for the existence of TCC, we have seen that it is proved for a vast range of graphs [12, 14]. Here we are going to see the same for some graph operations namely the join of graphs and the lexicographic product of graphs.

The paper is organized as follows.

In the second section, we obtain a bound for the total chromatic number of the join two graphs and we verify TCC for $G\vee G$, when G satisfies TCC. As a result, we prove that $\displaystyle \bigvee _{i=1}^{2^m}G_i$ satisfies TCC if $G_i\cong G$ for $1\le i\le 2^m$ and G satisfies TCC. Also, we verify weak TCC for the join of two graphs under certain constraints and we prove that the join of two type-1 graphs with same order satisfies TCC. Moreover, we prove $G\vee H$ is not a type-1 graph if G and H are regular graphs with same odd number of vertices. In addition, we prove that $C_n\vee C_m$ satisfies TCC, for any positive integers m and n.

In the third section, we produce an upper bound for the total chromatic number of the generalized join of graphs and hence we obtain an upper bound for the total chromatic number of the lexicographic product $G\circ H$ if H satisfies TCC. And in particular we verify weak TCC for the lexicographic product of a graph with the compliment of a complete graph.

2 TCC for Join of Graphs

In this section, we first recall the Konig’s Theorem.

Theorem 1

(Konig [6]). For any bipartite graph, $\chi '(G) = \varDelta (G)$.

The following result gives a bound for the total chromatic number of the join of two graphs.

Theorem 2

Let G and H be graphs with m and n vertices, respectively. If $\chi '(G)\le \chi _T(H)$, then

$$max\{\varDelta (H)+m,\varDelta (G)+n\}+1\le \chi _T(G\vee H)\le max \{m,n\}+\chi _T(H)+\chi (G).$$

In general, $max\{\varDelta (H)+m,\varDelta (G)+n\}+1\le \chi _T(G\vee H)\le max \{m,n\}+max\{\chi '(G),\chi '(H)\}+\chi (H)+\chi (G).$

Proof

Let r = max $\{m,n\}$, s = $\chi (G)$ and t = $\chi _T(H)$. The lower bound is clear from the definition of join of graphs. For proving the upper bound, we construct a total coloring of $G\vee H$ using $r+s+t$ colors.

First, we color the vertices and edges of G and H. Let c be a total coloring of H using t colors, say $1,2,\dots ,t$. It is given that $\chi '(G)\le \chi _T(H)$. Hence we can color the edges of G with some or all colors from $1,2,\dots ,t$. Then color the vertices of G with new s colors, say $t+1,t+2,\dots ,t+s$. Thus, we colored the vertices and edges of G and H using $t+s$ colors properly.

Next, we color the uncolored edges of $G\vee H$ and they are precisely the edges between G and H and hence the subgraph induced by these edges form a bipartite graph with maximum degree r. Hence by Theorem 1, it can be colored properly using new r colors, say $t+s+1,t+s+2,\dots ,t+s+r$. So we get a total coloring of $G\vee H$ using $r+s+t$ colors and therefore the result follows. The proof of second part is similar to that of the first one.

As an immediate consequence of Theorem 2, we have the following Corollary.

Corollary 1

If G is a bipartite graph and H is a graph satisfying TCC and both having the same maximum degree, then $\chi _T(G\vee H) \le \left\{ \begin{array}{rcl}k+4 &{} \text{ if }&{} H ~is~ type-2; \\ k+3&{}\text{ if }&{} H~ is~ type-1, \end{array}\right.$ where $k=\varDelta (G\vee H)$.

Proof

Let the maximum degree of both G and H be $\varDelta$. Then, by Theorem 1, $\varDelta =\chi '(G)< \varDelta +1\le \chi _T(H)$ and $\chi (G)=2$. By Theorem 2, we have $\chi _T(G\vee H)\le max\{m,n\}+\chi _T(H)+2$.

First, if G is type-1, then $\chi _T(G\vee H)\le max\{m,n\}+\varDelta (G)+1+2$ and hence $\chi _T(G\vee H)\le \varDelta (G\vee H)+3$.

Next, if G is type-1, then $\chi _T(G\vee H)\le max\{m,n\}+\varDelta (G)+2+2$ and thus $\chi _T(G\vee H)\le \varDelta (G\vee H)+4$.

One can ask the following question.

Problem 1. When does the join two graphs satisfy k-TCC, for some $k\ge 2$?

The following results will give some partial answers to this. For proving these partial answers, we need the following Lemma. For a matching M of G and $v\in V(G)$, we say v is M-saturated if v is incident with some edge in M. Otherwise, v is called M-unsaturated.

Lemma 1

The edge set of $K_{n,n}$ can be partitioned into $n+1$ matchings such that each vertex of $K_{n,n}$ is saturated by n matchings among them.

Proof

Let $X=\{u_1,u_2,\dots ,u_n\}$ and $Y=\{v_1,v_2,\dots ,v_n\}$ be the partition of $K_{n,n}$. Let $M_0 = \{u_iv_i : 1\le i\le n\}$ and $R_0=K_{n,n}-M_0$.

First, we successively define $R_j$’s and $M_j$’s as follows, for $1\le j\le n-2$,

$$\begin{array}{l} R_j' = R_{j-1}-\{u_j,v_j\}, M_j = A_j\cup B_j, \text { where }\\ A_j = \{u_iv_{i+j+1(mod~ n)} : 1\le i\le j-1 ~or~ i=n\},\\ B_j = \{u_iv_{i+j(mod~ n)} : j+1\le i\le n-1\} \text { and}\\ R_j = R_{j-1}-M_j.\end{array}$$

Next, we define

$$\begin{array}{l} R_{n-1}'=R_{n-2}-\{u_{n-1},v_{n-1}\},\\ M_{n-1}=\{u_iv_{2i+1(mod~ n)} : 1\le i\le n ~and~ i\ne n-1\},\\ R_{n-1}=R_{n-2}-M_{n-1}\text { and}\\ R_n'=R_{n-1}-\{u_n,v_n\},\\ M_n = \{u_iv_{2i (mod~ n)} : 1\le i \le n-1\}.\end{array}$$

Clearly, $M_j$ is a matching in $R_j'$, for $1\le j\le n$ and there are $n+1$ matchings including $M_0$. Also note that each vertex $u_j$ (as well as $v_j)$ in $K_{n,n}$ is $M_i$-saturated for all $i\in \{1,2,\dots ,n\}\backslash \{j\}$, $|M_0| = n$, $|M_j| = n-1$ for $1\le j \le n$ and $E(R_n')\backslash M_n=\emptyset$. Hence $\sum _{j=0}^{n}|M_j| = |E(K_{n,n})|$.

Finally, we have to prove $\{M_j\}_{j=0}^n$ are disjoint.

Clearly, $M_0\cap M_j = \emptyset$, for $j\in \{1,2,\dots ,n\}$. First, if there exist $j_1, j_2 \in \{1,2,\dots ,n-2\}$ and there exist $i,k \in \{1,2,\dots ,n\}$ such that $j_1\ne j_2$ and $u_iv_k\in M_{j_1}\cap M_{j_2}$. Then, $i\ne j_1,j_2$ and $u_iv_k\in (A_{j_1}\cap A_{j_2})\cup (A_{j_1}\cap B_{j_2})\cup (B_{j_1}\cap A_{j_2})\cup (B_{j_1}\cap B_{j_2})$.

When $u_iv_k \in A_{j_1}\cap B_{j_2}$, we have $i+j_1+1$ (mod $n) = k = i+j_2$ (mod n), by the definition of $A_{j_1}$ and $B_{j_2}$. Hence $j_1 = j_2-1$ (as $|j_1-j_2|<n$). Also, $1\le i \le j_1-1$ or $i=n$ and $j_2+1\le i\le n-1$. In both cases, it is not possible.

When $u_iv_k\in A_{j_1}\cap A_{j_2}$, we have $i+j_2+1$(mod $n) = k = i+j_1+1$(mod n). That means, $j_2=j_1$ (as $j_1$ and $j_2$ are less than n), which is a contradiction.

When $u_iv_k\in B_{j_1}\cap B_{j_2}$, we have $j_1 = j_2$, which is not possible.

When $u_iv_k\in B_{j_1}\cap A_{j_2}$, then $j_2=j_1-1$ and $j_1+1\le i\le n-1$ and $1\le i\le j_2-1$, which is a contradiction.

So, for any two distinct $j_1,j_2 \in \{1,2,\dots , n-2\}, M_{j_1}\cap M_{j_2}=\emptyset$. Similarly, we can show that $M_j$’s, $M_{n-1},$ and $M_n$ are disjoint for $j\in \{0,1,2,\dots ,n-2$}. Therefore $\{ M_j\}_{j=1}^n$ are disjoint. Hence the result the follows.

Now, using Lemma 1, we prove that TCC is true for the join of a graph satisfying TCC with itself.

Theorem 3

If G is a graph satisfying TCC, then $G\vee G$ satisfies TCC.

Proof

Let $V(G)=\{u_1,u_2,\dots ,u_n\}$ and $\varDelta (G) = k$. Then $\varDelta (G\vee G) = n+k$ and the graph $G\vee G$ can be considered as the union of three induced sub-graphs, that is two copies of G, say $G_1$ with vertex set $\{u_1,u_2,\dots ,u_n\}$, $G_2$ with vertex set $\{v_1,v_2,\dots ,v_n\}$ (i.e., $v_i\in V(G_2)$ is the corresponding vertex of $u_i\in V(G_1)$) and the edges between $G_1$ and $G_2$ (the induced subgraph of these edges is $K_{n,n}$). In order to verify TCC for $G\vee G$, we need to show that there is a total $(n+k+2)$-coloring of $G\vee G$.

Let c be a total coloring of G with $k+2$ colors, say $1,2,\dots , k+2$. First we color the vertices and edges of $G_1$ totally and then color the edges of $G_2$ using c. Next, we color the edges between $G_1$ and $G_2$ by using Lemma 1 and finally, we assign colors to the vertices of $G_2$.

As the edges of $G_1$ are colored properly under c, we color the edges of $G_2$ also using c as follows. For $v_iv_j\in E(G_2)$, $c(v_iv_j)= c(u_iu_j)$. For $i\in \{1,2,\dots ,n\}$, we define $c_i \in \{1,2,\dots ,k+2\}$ such that $c_i$ is not represented at $u_i$ in $G_1$, that is, $c_i$ is not assigned to any of the elements in $\{u_ix : x\in N_{G_1}(u_i)\}\cup \{u_i\}$. Such a color $c_i$ will always exist as c is a $(k+2)$-total coloring of G and $|\{c(u_ix): x\in N_{G_1}(u_i)\}\cup \{c(u_i)\}|\le k+1$. By Lemma 1, we assign the total coloring $c'$ to the vertices and edges of $G\vee G$ using c as follows. For $1\le i\ne j\le n ,$

$$c'(x) = \left\{ \begin{array}{rcl}c(x) &{} \text{ if }&{}x=u_i, ~ x=u_iu_j\in E(G_1)~\text{ or }~x=v_iv_j\in E(G_2)~; \\ k+2+j &{}\text{ if }&{}x=v_j~ \text{ or } ~x\in M_j~ ; \\ c_i&{}\text{ if }&{}x=u_iv_i\in M_0. \end{array}\right. $$

Then $c'$ colors the vertices and edges of $G\vee G$ using $n+k+2$ colors.

Finally, we need to verify that $c'$ is proper. Note that for $x\in V(G_1)\cup E(G_1)\cup M_0\cup E(G_2),~ c'(x)\in \{1,2,\dots , k+2\}$ and for $i,j\in \{1,2,\dots , n\}$ with $i\ne j,~ c'(u_iv_j),~c'(v_j)\in \{k+3, k+4,\dots , n+k+2\}$. Since $c'=c$ on $V(G_1)\cup E(G_1)\cup E(G_2)$, $M_i$’s are matchings such that $u_i's$ and $v_i's$ are $M_i$-unsaturated and by the definition of $c_i$, we have $c'$ is proper. Hence the results follows.

By Theorem 3 and applying induction on t, we have the following corollary.

Corollary 2

If a graph G satisfies TCC, then $\displaystyle \bigvee _{i=1}^{m}G_i$ satisfies TCC, where $G_i\cong G$ for $1\le i\le n$ and $m=2^t$ for any positive integer t.

For two distinct graphs we cannot adopt the same method of proof since the missing colors in the corresponding vertices need not be same as in the above case. So, next we prove the validity of weaker version of TCC for the join of two graphs under certain restrictions.

Theorem 4

If G and H are two graphs with m and n vertices respectively. Also, $\varDelta (G)\ge \varDelta (H)$, $m\le n$ and G satisfies TCC, then $\chi _T(G\vee H)\le \varDelta (G\vee H)+3$.

In the other case, that is for $m\ge n$, adding isolated vertices in H and taking the join will results in a new graph whose maximum degree is different from that of our original $G\vee H$. Hence this method is not valid in that case. We now prove the following result on regular graphs with odd number of vertices.

Theorem 5

If G and H are two k-regular graphs with same odd order n, then $G\vee H$ is not type-1.

The equality of the number of vertices in both graphs plays a crucial role in the proof and hence in the cases of unequal number of vertices we cannot use this pattern. The following corollaries are the immediate consequences of Theorem 5 and Theorem 3.

Corollary 3

For an odd ordered regular G graph satisfying TCC, the join $G\vee G$ is type-2.

Corollary 4

For an odd positive integer $m\ge 3$, $C_m\vee C_m$ is a type-2 graph.

The following result gives the validity of TCC for the join of two cycles.

Proposition 1

For $m,n \ge 3$, the join of two cycles $C_m \vee C_n$ satisfies TCC .

Proof

Let $G = C_m \vee C_n$. Clearly, $\varDelta (G) = max\{m,n\}+2$. Let $V(C_m) = \{u_1,u_2,\dots ,u_m\}$ and $V(C_n) = \{ v_1,v_2,\dots ,v_n\}$. Without loss of generality, let us assume $m\ge n$. For $m=n=3$, by Theorem 3 the result follows. So let us assume that, $m> 3$ and $n\ge 3$. We have to show that there exists a total coloring of G using $\varDelta (G)+2$ colors, where $\varDelta (G)=m+2$.

Case 1. (m and n are even)  

The following is a total coloring of G using $m+4$ colors.

Clearly, the subgraph induced by the uncolored edges forms a bipartite graph of maximum degree m and hence using Theorem 1 we can properly color those edges using m new colors and hence the result follows.

Case 2. (m and n are odd)  

Consider the following coloring of G,

Next, we color some of the edges in between $C_m$ and $C_n$.

For $1\le i\le n,~ c(u_iv_i) = 3$ and for $0\le k\le n-1$,

$c(u_{m-k}v_{n-k}) = \left\{ \begin{array}{rcl}6 &{} \text{ for }&{} 1\le k\le n-1; \\ 1&{}\text{ for }&{} k=0. \end{array}\right.$

The subgraph induced by the remaining uncolored edges forms a bipartite graph with maximum degree $m-2$ and hence the result follows from Theorem 1.

Case 3. (m is even and n is odd.)  

We color the vertices an edges of $C_m$ and $C_n$ as follows:

Next, we color some edges between $C_m$ and $C_n$. For $1\le i \le n-1$, color $c(u_iv_i) = 5$ and also for $i=n$, color $c(u_{i+1}v_i)=1$. Then the subgraph induced by the remaining uncolored edges form a bipartite graph of maximum degree $m-1$ and by Theorem 1, the result follows.

Case 4. (m is odd and n is even.)  

First, we color the vertices and edges of both $C_m$ and $C_n$ using,

For $1\le i \le n$, color $c(u_iv_i)=3$. As $m>n$, the subgraph induced by the remaining uncolored edges form a bipartite graph of maximum degree $m-1$. Hence the result follows.

As an immediate consequence of Proposition 1, we have the following corollary.

Corollary 5

([16]). For any positive integers m and n, $P_m\vee P_n$ satisfies TCC.

3 Total Coloring of the Generalized Join of Graphs

In this section, we give an upper bound for the total chromatic number of $G[H_1,H_2,\dots ,H_n]$. Let G be a class-1 graph. Then $E(G)=\displaystyle \bigcup _{i=1}^{k} M_i$, where $M_i$’s are disjoint matchings. Let r be the least number in $\{1,2,\dots ,k\}$ such that every vertex of G is saturated by at least one of the matchings $M_{i_1},M_{i_2},\dots ,M_{i_r}$. Without loss of generality, we relabel $M_{i_j}$ by $M_j$ for $1\le j\le r$.

Theorem 6

Let G be the above mentioned graph with n vertices and $\{H_1,H_2,\dots , H_n\}$ be a set of graphs with $H_i\vee H_j$ satisfying TCC, for each $i,j\in \{1,2,\dots ,n\}$, then $\chi _T (G[H_1,H_2,\dots ,H_n])\le \displaystyle \sum _{i=1}^{r}s_i + \displaystyle \sum _{j=r+1}^{k}t_j$, where $s_j = max\{\varDelta (H_x\vee H_y) +2 ~|~ xy\in M_j\}$ for $1\le j\le r$ and $t_j = max \{max\{|V(H_x)|,|V(H_y)| ~\vert ~xy\in M_j \}\}$ for $r+1 \le j\le k$.

The following corollary is a consequence of Theorems 3 and 6.

Corollary 6

If H is any graph satisfying TCC with m vertices, then

$$\chi _T(G\circ H) \le \left\{ \begin{array}{rcl}\varDelta (G\circ H)+\varDelta (H)(\varDelta (G)-1)+2\varDelta (G) &{} \text{ if }&{} G ~is~ class-1 \\ \varDelta (G\circ H)+ \varDelta (G)\varDelta (H)+2(\varDelta (G)+1)+m &{}\text{ if }&{} G ~is~ class-2 \end{array}\right. $$

Proof

Clearly, $G\circ H \cong G[H_1,H_2,\dots ,H_n]$, where $H_i\cong H$ for $1\le i\le n$ and $\varDelta (G\circ H)=\varDelta (H)+\varDelta (G)m$. By Theorem 3, $H\vee H$ satisfies TCC. Then by Theorem 6, $s_j=\varDelta (H)+m+2$, for $1\le j\le r$ and $t_j= m$, for $r+1\le j\le \chi '(G)$. By Theorem 6, $\chi _T(G\circ H) \le \varDelta (H) r+2r+m\chi '(G) \le (\varDelta (H)+m+2)\chi '(G)$.

If G is a class-1 graph, then $\chi '(G)=\varDelta (G)$. So, $\chi _T(G\circ H) \le (\varDelta (H)+m+2)\varDelta (G) \le \varDelta (G\circ H)+\varDelta (H)(\varDelta (G)-1)+2\varDelta (G)$.

If G is class-2, then $\chi '(G)=\varDelta (G)+1$. So, $\chi _T(G\circ H) \le (\varDelta (H)+m+2)(\varDelta (G)+1) \le \varDelta (G\circ H)+ \varDelta (G)\varDelta (H)+2(\varDelta (G)+1)+m$. Hence the result follows.

As the bound above is a weaker one, we replace our H with the compliment of complete graph and obtain the following result.

Theorem 7

If G satisfies TCC with m vertices, then $G[K_n^c]$ satisfies weak TCC. In particular, if G is type-1, then $G[K_n^c]$ satisfies TCC.

4 Concluding Remarks and Open Problems

In this paper, one of our aims was to prove the validity of TCC for co-graphs by showing that TCC is valid for the join of any two graphs. But we could find some partial answers only and the TCC for the join of any two arbitrary graphs is still open. Also, we obtained a bound for the total chromatic number of G-generalized join of graphs and as a consequence we obtain an upper bound for the total chromatic number of the lexicographic product $G\circ H$.