Total colorings of glued graphs

Abstract

The Total Coloring conjecture states that for every graph G, X"(G) ≤ ∆(G)+2 when X"(G) is the total chromatic number of G and ∆(G) is the maximum number of degree of vertices of G. We say that a graph G is of type 1 if X"(G) = ∆(G)+1 and type 2 if X"(G) = ∆(G)+2. In this thesis, upper bounds of the total chromatic number of glued graphs in terms of the total chromatic number of original graphs are presented. We investigate that total chromatic number of glued graphs of same class where the classes are cycles, trees, bipartite graphs and complete graphs and prove that these glued graphs satisfy the Total Coloring Conjecture and obtain necessary and sufficient conditions for these glued graphs except the glued graph of bipartite graphs to be either of type 1 or type 2. Furthermore, we study sufficient conditions for any graph to satisfy the Total Coloring Conjecture and be either type 1 graph or type 2 graph and use these conditions to obtain the result of glued graphs of any graph and any tree.