Total Coloring of Some Graph Operations

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.