Total Coloring Conjecture for Certain Classes of Product Graphs

Abstract

A total coloring of a graph is an assignment of colors to all the elements of the graph in newlinesuch a way that no two adjacent or incident elements receive the same color. Minimum newlinenumber of colors required for a total coloring of a graph G is called the total chromatic newlinenumber, it is denoted by and#967;and#8242;and#8242;(G). It is clear that and#967;and#8242;and#8242;(G) and#8805; _(G)+1, where _(G) is the maximum degree of G. Behzad and Vizing independently conjectured (Total Coloring Conjecture (TCC)) that for every graph G, and#967;and#8242;and#8242;(G) and#8804; _(G)+2. A graph G is said to be total colorable, if the elements of G are colored with at most _(G) + 2 colors. Graphs that need only _(G) + 1 colors are called graphs of Type I. Graphs that need _(G) + 2 colors are called graphs of newlineType II. Total coloring conjecture is one of the well known conjectures in graph theory. newlineProduct graphs are well known classes of graphs. Many people studied the structure of newlinevarious product graphs. In this thesis, the total chromatic number for certain classes newlineof product graphs and other classes of graphs are obtained. In particular, the following newlineproblems are considered: (i) Total coloring conjecture for vertex, edge and neighborhood corona products of graphs. (ii) Total coloring conjecture for deleted lexicographic product of graphs. (iii) Total coloring conjecture for Indu-Bala product graph, skew and converse skew newlineproduct of graphs. (iv) Total coloring conjecture for core-satellite, cocktail party, modular product and clique expansion graphs. A detailed literature review related to the above classes of graphs are given in this thesis. The first problem is to prove the vertex corona, edge and neighborhood corona products of graphs are Type I. Secondly, we prove that the deleted lexicographic product graphs are total colorable. Thirdly, we showed that the Indu-Bala product graph, skew and converse skew products, cover, clique cover and comb products of graphs are total colorable. In particular, we proved that certain classes of the above graphs are Type I.Finally, we considered the core-satellite...