Approximation algorithms for the achromatic number
The achromatic number for a graph G=?V,E? is the largest integer m such that there is a partition of V into disjoint independent sets {V1,?,Vm} such that for each pair of distinct sets Vi, Vj, Vi?Vj is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math.38, 364?372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.