Types Of Join Graph Coloring Research

The total colouring of a graph G is to colour both the vertices and the edges of G. The total chromatic number x_T(G) is the minimum number of colors need to color the vertices and the edges of G such that no adjacent or incident pair of elements receive the same color. Since a vertex with maximum degree is incident with A edges which require A colors plus another color for the vertex, x_T(G)>△(G)+1.The Total Coloring Conjecture (TCC), proposed by Behzad in 1965, claims that for any graph G,x_T(G)≤ △ (G)+2.Up to now, the TCC was proved true for a few classes of graphs. At the same time, people try to determine the total chromatic number of a graph. A graph G is said to be of Type 1 if x_T(G)=△(G)+1 and Type 2 if x_T(G)=△(G)+2. In this paper, we prove a few classes of joins satisfy TCC and determine their total chromatic numbers.In chapter 1, we give some concepts and theorems about total coloring. The main result of chapter 2 is to give a complete classification of the join of O_m and C_n based on their total chromatic numbers. In chapter 3 it is proved that the join of K_n1,n2 and P_m is of Type 1, where n₁2. The main objectives of chapter 4 are: (i) to prove that the joins of K_n1,n2 and C_m is of Type 1, where n₁2 and m≠n₁+2; (ii) to prove the joins of K_m,n and C_n is of Type 1.