On Approximating the Achromatic Number

Source abstract

The achromatic number problem is to legally color the vertices of an input graph with the maximum number of colors, denoted $\psi^*$, 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 a ratio of $O(n\cdot \log\log n/\log n)$. This improves over the previously known approximation ratio of $O(n/\sqrt{\log n})$, due to Chaudhary and Vishwanathan [{\it Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms}, New Orleans, LA, 1997, pp. 558--563]. For graphs of girth at least 5 we give an algorithm with an approximation ratio $O(\min\{n^{1/3},\sqrt{\psi^*}\})$. This improves over an approximation ratio $O(\sqrt{\psi^*})=O(n^{3/8})$ for the more restricted case of graphs with girth at least 6, due to Krysta and Lory{ś [Proceedings of the Seventh Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci. 1643, Springer-Verlag, Berlin, 1999, pp.402--413]. We also give the first hardness result for approximating the achromatic number. We show that for every fixed $\epsilon > 0$ there is no $2-\epsilon$ approximation algorithm, unless P=NP.