TOTAL COLORINGS OF SOME CLASSES OF GLUED GRAPHS

Abstract

′′

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 chromatic number χ (G) of a graph G is the minimum

The Total Coloring Conjecture states that for every simple graph G, ′′ ′′

χ (G)≤Δ(G)+2. AgraphGisoftype1 ifχ (G)=Δ(G)+1andof ′′

type 2 if χ (G) = Δ(G) + 2. A glued 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 com- plete graphs satisfy the Total Coloring Conjecture. Moreover, we inves- tigate necessary and sufficient conditions for being either of type 1 or type 2 of the glued graphs of cycles, trees and complete graphs.