We improve here the expected performance of parallel algorithms for graph coloring. This is achieved through new adaptive techniques that may be useful for the average-case analysis of many graph algorithms. We apply our techniques to: the class G n,p of random graphs. We present a parallel algorithm which colors the graph with a number of colors at most twice its chromatic number and runs in time O(log4 n/ log log n) almost surely, for p = Ω((log(3) n)2/ log(2) n). The number of processors used is O(m) where m is the number of edges of the graph. the class of all k-colorable graphs, uniformly chosen. We present a parallel algorithm which actually constructs the coloring in expected parallel time O(log2 n), for constant k, by using O(m) processors on the average. This problem is not known to have a polynomial time algorithm in the worst case.