On approximating the achromatic number

The achromatic number problem is to legally color the vertices of an input graph with the maximum number of colors, denoted &psgr;*, so that every two color classes share at least one edge. This problem is known to be NP-hard. For general graphs we give an algorithm that approximates the achromatic number within ratio of &Ogr;(n -log log n/ log n). This improves over the previously known approximation ratio of &Ogr; (n/Vlog n), due to Chaudhary and Vishwanathan [4]. For graphs of girth at least 5 we give an algorithm with approximation ratio &Ogr;(min{n^1/3, V&psgr;*}). This improves over an approximation ratio &Ogr;(V&psgr;*) = &Ogr;(n^3/8) for the more restricted case of graphs with girth at least 6, due to Krista and Lorys [13]. We also give the first hardness result for approximating the achromatic number. We show that for every fixed □ > 0 there in no 2 - D approximation algorithm, unless P = NP.