【作者】 孙宜蓉；

【导师】 刘信生； 陈祥恩；

【作者基本信息】 西北师范大学 ， 应用数学， 2004， 硕士

【摘要】 本文共分四个部分。 第一部分主要是引入一些在本文中经常出现的的基本概念和主要性质，并对某些概念给出具体实例。 第二部分介绍了第一矩量原理，Markov不等式以及四种形式的Lov(?)sz局部引理的内容，给出了这几种概率方法在超图上的应用，用几种思路找到了超图存在2-可染色的不同条件，其中着重对一般形式的Lov(?)sz局部引理给出应用实例，即无圈边染色，证明了当图G的围长大于等于700ΔlogΔ时，图G的无圈边色教小于等于△+2然后，用概率论的方法证明了几种形式的Lov(?)sz局部引理，并从中发现几种Lov(?)sz局部引理之间的关系，找出其不同的适用范围。 第三部分主要讨论了邻点可区别的边染色这一概念，用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的边色数。 第四部分引入了邻点可区别的全染色这一新的概念，并用第一矩量原理，Markov不等式以及几种形式的Lov(?)sz局部引理分别得到了任一最大度为d的图G的邻点可区别的全色数。更多还原

【Abstract】 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.更多还原