On Two Topics In Total Dominator Colorings Of Graphs

Let G be a simple graph.A proper k-coloring of G is an assignment of colors to vertices of G such that any two adjacent vertices receive distinct colors.The smallest integer k such that G has a k-coloring is the chromatic number of G,de-noted by ?(G).A total dominating set of G without isolated vertex is a set S of vertices such that every vertex in G is adjacent to at least one vertex in S.The total domination number of G is the minimum cardinality of a total dominating set of G,denoted by ?t(G).A total domination coloring of a graph G is the general-ization of the vertex coloring and total dominating set.Let G be a graph without isolated vertices,a total domination coloring of a graph G is a proper coloring of G in which each vertex of the graph is adjacent to every vertex of some(other)color class.The total dominator chromatic number of G is the minimum number of color classes in a total domination coloring of G,denoted by ?dt(G).In 2015,Kazemi el at.give a result that the total dominator chromatic number of a connected graph G without isolated vertex is between 2 and n,i.e.2 ??dt(G)?n.At the same time,they characterizes the graphs with the total dominator chromatic number of 2 or n.In the same paper,Kazemi el at.also proved that total dominator chromatic number is NP-hard.Recently,A result of Bagan showed that determining ?dt(G)is polynomial-time solvable for P4-sparse graphs.The thesis consists of four chapters,we mainly study the total dominator chro-matic number of special graphs.In chapter 1,we mainly introduce the background and significance of graph coloring problems,some basic concepts and symbols to be used in this paper,ex-pound the dominator coloring and the total dominator coloring problems theory research and list the main results of this paper.In chapter 2,we characterize the graphs with the total dominator chromatic number of 3,n-1 and n-2.In chapter 3,we study the total dominator coloring of two classes of P4-restricted graphs.Firstly,for the total dominator chromatic number of P4-reducible graphs,we analyze the structure of the P4-reducible graphs and give a computing method of the total dominator chromatic number of P4-reducible graphs,and get a conclusion that the total dominator coloring number of P4-reducible graphs is polynomial-time solvable.secondly,for the total dominator chromatic number of P4-tidy graphs,we analyze the structure of the P4-tidy graphs and give a comput?ing method of the total dominator chromatic number of P4-tidy graphs,and give a polynomial time algorithm of the total dominator chromatic number of P4-tidy graphs.In the last chapter,we summarized the conclusions about total dominator col-oring in this paper and indicated some further research problems.