On coloring problems with respect to domination in graphs

Abstract

This thesis deals with proper coloring of graphs subject to certain constraints based on the concepts of domination. Extending the concepts of dominator coloring and global dominator coloring, the present study introduces and study three domination related colorings are namely: total global dominator coloring, total domination coloring and anti-dom-coloring. A total global dominator coloring (tgd-coloring) of a graph G is a coloring in which every vertex of G has a proper dom-color class and an antidom-color class. The proper dom-color class of a vertex v is a color class in which every vertex in it is adjacent to v while the anti-dom-color class of v is a color class in which none of the vertices in it is dominated by v. Total global dominator chromatic number of a graph G, denoted by and#967;tgd(G), is the minimum number of colors required for a tgd-coloring of G. A detailed study of the parameter and#967;tgd(G) has been carried out and the results include newlinebounds of and#967;tgd(G) and its relation with the other graph parameters of G such as o(G), and#967;(G), and#947;(G), and#967;t d(G), and#947;g(G), and#967;gd(G) etc. The total global dominator chromatic number of several graph classes such as paths, cycles, complete bipartite graphs, trees, and unicyclic graphs have been determined. The study also deal with the tgd-coloring of Mycielskian graphs, derived graphs such as helm graphs, web graphs, sun graphs, closed suns graph etc. and values of and#967;tgd(G) when G newlineis graph obtained by some graph operations such as union of graphs, corona of graphs and join of graphs. A total domination coloring of a graph G is a coloring in which every vertex has a proper dom-color class and each of the color classes is dominated by some newlinevertex of G. The minimum number of colors required for the total domination coloring of G is said to be the total domination chromatic number of G, denoted by and#967;td(G). The relation of and#967;td(G) with and#967;(G), and#947;(G), and#947;t(G), and#967;t d(G) etc. are determined.