Three Kinds Of Colorings Of Graphs And The Probabilistic Method

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.