Probabilistic Method And Colorings Of Graphs

There are four parts in this paper.In the first part, we introduce some fundamental concepts and main properties that often used in the paper. Some examples which are directed towards some concepts are given.In the second part, we introduce the First Moment Principle. Markov's Inequality and four kinds of Lovasz Local Lemma, and give different applications in hypergraphs with these probabilistic methods, we find different conditions for a hypergraph to be 2-colorable with some kinds of thinkings. Among them the applications with the general Local Lemma arc the most important, such as acyclic edge colorings of graphs. We prove that the acyclic edge chromatic number of G is less than or equal to A + 2 for any graph G whose girth is at least 700â–³logâ–³. We prove four kinds of Lovasz Local Lemma with the method of probability theory and discuss the relationship among them and their different applicable ranges.In the third part, we discuss ''adjacent-vertex distinguishing edge colorings". We obtain the adjacent-vertex distinguishing edge chromatic numbers with the First Moment Principle. Markov's Inequality and some kinds of Lovasz Local Lemma, respectively.In the last part, we discuss a new concept "adjacent-vertex distinguishing total colorings". We obtain the adjacent-vertex distinguishing total chromatic numbers with the First Moment Principle, Markov's Inequality and some kinds of Lovasz Local Lemma, respectively.