The Total-Coloring Critical Graph And Adjacent-Vertex-Distinguishing Total Coloring

The coloring problems is one of popular problems in graph theory because of its profound significance and combinatorial analysis can be translated into the problem of graph which don'tcontain a certain graph G as a subgraph depends on the chromatic number of the graph.Therefore T R.Jensen and B.Toft asserted:the graph coloring theory in discrete mathematics at the center position.In real life,many areas will be dealt with the object of a certain set of rules according to certain classification of the problem.For example,time-table problem,the problem of storing,task allocation, schedule,scheduling,circuiting arrangementand so on.These problems are closely related to coloring theory.The graph coloring is refers speaking of the graph in the vertex,edge(to the plane graph also the face)and so on the element carries on the classification according to the certain rule.Object dissimilarity or rule dissimilarity,then has all kinds of colorings, such as vertex coloring,edge coloring,total coloring,strong coloring,adjacent strong edge coloring,adjacent vertex-distiguishing total coloring,vertex- distiguishing edge coloring,edge-face coloring,perfect coloring and so on many kinds of of coloring ways.In order to properly express large-network,storage,the timing and allocation of research topics such as the relationship between the elements.Graph coloring theory staining as a viable tool for the introduction by the natural.Because of its good application background,graph coloring theory has become one of the rapid development branaches of the modern graph field.While discussing coloring problems,one kind of special graph-critical graph have an important effect.In the first chapter,the paper studies total-coloring critical graph. The total-coloring critical graph includes the total-coloring vertex critical graph and edge critical graph,but we mainly analysis the structure properties of the total-coloring edge critical graph,do further promotes on the basis of the result that the paper[2] gave out and show the general conclusion.In the second chapter,we draw into adjacent vertex-distinguishing total coloring. Adjacent vertex-distinuishing total coloring is the latest theory of a research direction, Zhang Zhongfu others put forword the concept of adjacent vertex-distinguishing total coloring,some results have been given,and brought up the conjecture:for every connected graph G with order at least 2.we have:X_at(G)≤△(G)+3.Now,results little known that there are many unsolved issues.This paper gives several types of graph adjacent vertex-distinguishing chromatic number,test and verify adjacent vertex-distinguishing chromatic conjecture.