Total Coloring of Circulant and Related Cayley Graphs

Abstract

Total coloring is a function which assigns colors to the vertices and edges of the graph, such newlinethat the adjacent and the incident elements receive different colors. The minimum number of newlinecolors required for a proper total coloring of a graph G is called the total chromatic number newlineof G, and is denoted by and#967;and#8242;and#8242;(G). It is easy to see that and#916;(G) + 1 and#8804; and#967;and#8242;and#8242;(G), where and#916;(G) is newlinethe maximum degree of G. Bezhad and Vizing independently proposed a conjecture called newlineTotal Coloring Conjecture, which states that for any graph G, and#967;and#8242;and#8242;(G) and#8804; and#916;(G)+2. The Total newlineColoring Conjecture (TCC) is a popular problem in this field, open for more than 60 years. newlineCayley graphs are graphs defined on an algebraic structure, typically groups, with adjacency newlinedetermined by left translation by the elements of a symmetric set, called the generating set. newlineCayley graphs have wide use within and outside graph theory. Circulant graphs are Cayley newlinegraphs defined on the cyclic group of finite order, the group of integers modulo n with respect newlineto addition. In this thesis, we prove the TCC for some classes of Cayley graphs, such as newlinecirculant graphs and power of cycles. Also, we have obtained tight bounds on the total newlinechromatic number for some classes of Cayley graphs. newline newline