【作者】 安明强；

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

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

【摘要】 本文通过归纳定义了图的三类染色一无圈染色，邻点可区别的染色和点可区别的染色。应用Lovász局部引理的赋权形式，讨论并得到了任一最大度△≥4的图G，其邻点可区别的无圈边色数至多为16△²。应用Lovász局部引理的一般形式，讨论并得到了任一最大度△≥32²ln5，最小度δ≥32（△ln△）^1/2的图G，其邻点可区别的全色数至多为2△+1+2（△ln△）^1/2；进一步，若全色数χ_t（G）≤△+2，则其邻点可区别的全色数至多为△+2+2（△ln△）^1/2。然后，通过具体构造染色的方法讨论并给出了路、圈、完全图、星、扇、轮的Mycielski图，路与圈的联图P_m∨S_n的点可区别的全色数。更多还原

【Abstract】 In this paper,by induction we define three kinds of colorings of graphs,which are acyclic coloring,adjacent vertex-distinguishing coloring and vertex-distinguishing coloring.With applying the weighted form of the Lovasz local lemma,we have discussed and obtained that the adjacent vertex distinguishing acyclic edge chromatic number is at most 16Δ² for any graph G with maximum degreeΔ≥4. With applying the general form of the Lovasz local lemma,we have discussed and obtained that the adjacent vertex distinguishing total chromatic number is at most 2Δ+1 + 2（ΔlnΔ）^1/2 for any graph G with maximum degreeΔ≥32²ln5 and minimum degreeδ≥32（ΔlnΔ）^1/2;furthermore,the adjacent vertex distinguishing total chromatic number is at mostΔ+ 2 + 2（ΔlnΔ）^1/2 if the total chromatic number X_t（G）≤Δ+ 2.Then with giving colorings of a graph, vertex distinguishing total chromatic numbers on Mycielski’s graphs of path,cycle,complete graph,star,fan and wheel,and vertex distinguishing total chromatic numbers of P_m∨S_n are discussed and given,respectively.更多还原