TOTAL COLORINGS OF SOME CLASSES OF GLUED GRAPHS

Abstract

The total chromatic number χ(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no incident or adjacent pairs of elements receive the same color. The Total Coloring Conjecture states that for every simple graph G, χ(G) ≤ Δ(G) + 2. A graphG is of type 1 if χ(G) = Δ(G) + 1 and of type 2 if χ(G) = Δ(G) + 2. Aglued graph results from combining two vertex-disjoint graphs by identifying connected isomorphic subgraphs of both graphs. We prove that the glued graphs of cycles, bipartite graphs and complete graphs satisfy the Total Coloring Conjecture. Moreover, we investigate necessary and sufficient conditions for being either of type 1 or type 2 of the glued graphs of cycles, trees and complete graphs