The achromatic number problem is: given as input an undirected simple graph G(V,E), to partition the vertices of the graph into the largest possible collection of independent sets so that, for any two independent sets I1, I2 in the partition, there exists at least one edge that goes from I1 to I2. This talk will discuss some details of the following results that were achieved in a joint paper with Krauthgamer and in another joint paper with Shende. For those who are not familiar with approximation algorithms, the necessary definitions will be given in the talk. \tThe problem admits a polynomial O(n log(log n)/log n) approximation algorithm. This result improved an O(n/√(log⁡n )) approximation by Chaudhary and Vishwanathan. \tGraphs of girth 5 admit an achromatic partition of size at least m/n. This is a new result in graph theory. \tGraphs of girth 5, admit a polynomial approximation algorithm of ratio O(min{n^(1⁄3),√opt}). This improves the result of Krysta and Lorys of O(min{n^(3⁄8),√opt}) that was proved only for graphs of girth 6. \tWe give a good ratio algorithm for bipartite graphs under some assumption. \tResult 4 is used in a paper with Shende to give an O(n^(4⁄5))) approximation algorithm for the achromatic number on bipartite graphs. \tUnless NPC problems have a fast algorithm, the achromatic number problem cannot be approximated within better than √(log⁡n )

. The talk is self contained.