Total colouring 2 1 total labeling and acyclic edge colouring of new classes of graphs

Abstract

This thesis comprises five chapters and is concerned with determining the total colouring the 2 1 total labeling and the acyclic edge colouring of certain new classes of graphs newlineA colouring of vertices and edges of a graph G is said to be a proper newlinetotal colouring of G if no two adjacent vertices no two adjacent edges and no newlinetwo incident elements receive the same colour The minimum number of colours newlinefor which there exists a proper total colouring for a given graph G is called the newlinetotal chromatic number of the graph G and is denoted by c00 G McDiarmid and newlineSanchez Arroyo McDiarmid and Sanchez Arroyo 1994 have shown that even newlinethe problem of determining the total chromatic number of k regular bipartite newlinegraphs is NP hard for each fixed k 3 newlineAn interesting and long standing famous conjecture on the total newlinechromatic number was posed by Behzad Behzad 1965 in 1965 which states newlinethat for any graph G c00 D G 2 Rosenfeld Rosenfeld 1971has shown newlinethat if G is any graph with D 3 then c00 G DG 2 Inspired by the result newlineof Rosenfeld here in this thesis we consider the following special classes of newlinegraphs with D 3 for determining the total chromatic number newline newline