On Graph Colorings With One Or More Distinguishing Constraints

Graph coloring is one of the most important problems in graph theory, it re-sults from computer science, and has a strong theoretical significance and practicalsignificance. Now, graph colorings are widely applied in the world, and will becomean important field where many researchers have concerned with. Up to now, onehave obtained many rich results, and these results are still under improvement.Based on adjacent vertex distinguishing total coloring, this thesis presents sev-eral concepts on graph colorings with N (N=2,3,4) distinguishing constraintsfor the first time. Through investigation, such graph colorings are not found andstudied in domestic and overseas. We have constructed our works in four chapters.In Chapter1, firstly, notations and terminologies of graph theory are introducedand defined. Secondly, we introduce some current states of graph colorings. Lastly,the main results in this thesis are listed.In Chapter2, we consider the problem of adjacent vertex distinguishing totalcoloring of graphs having smaller degrees and compound intersecting cycles, and theadjacent vertex distinguishing total chromatic number of these two kinds of graphshave been obtained.In Chapter3, we present new graph colorings with N (N=2,3,4) distinguishingconstraints as follows:(2)-vertex distinguishing total coloring;(3)-adjacent vertex distinguishing total coloring;(4)-adjacent vertex distinguishing total coloring;(4)-vertex distinguishing total coloring. Based on the above graph colorings, trees, paths, cycles, complete bipartitegraphs, P2∨Pn, generalized Petersen graphs, stars, fans, wheels and double starshave been studied in this thesis. We determine:(2)-vertex distinguishing total chromatic number of trees;(3)-adjacent vertex distinguishing total chromatic number of P2∨Pnandcomplete bipartite graphs;(4)-adjacent vertex distinguishing total chromatic number of paths, cycles,complete bipartite graphs and generalized Petersen graphs;(4)-vertex distinguishing total chromatic number of stars, fans, wheels anddouble stars.In Chapter4, we give some further researching problems of graph coloring.My innovations are to propose:(1) total colorings of graphs with mixed vertex distinguishing constraints;(2) two conjectures:conjecture1: χ′′(3)as(G)≤(G)+3.conjecture2: χ′′(4)as(G)≤(G)+4.