Efficient approximation algorithms for the achromatic number (Q4938783)

The achromatic number of a graph is the maximum size \(k\) of a vertex coloring of the graph, where every pair of the \(k\) colors is assigned to some two adjacent vertices and adjacent vertices are colored with different colors. It is well known that the achromatic number problem is NP-complete even for bipartite graphs or for trees. An \(\alpha \)-approximation algorithm for a maximization problem \(P\) is a polynomial time algorithm, that always computes a solution to the problem \(P\), whose value is at least a factor \(\frac{1}{\alpha }\) of the optimum. In this paper improved polynomial time approximation algorithms for the achromatic number problem on graphs with large girth and for trees, and linear time approximation algorithms for trees with bounded maximum degree are presented (e.g., a 2-approximation algorithm for trees, an \(O(n^{3/8})\)-approximation algorithm for graphs with girth at least six or an asymptotic 1.155-approximation linear time algorithm for binary trees). Also the lower bound of \textit{M. Farber, G. Hahn, P. Hell} and \textit{D. Miller} [J. Comb. Theory, Ser. B 40, 21-39 (1986 Zbl 0558.05024)] for the achromatic number of trees with maximum degree bounded by three is improved. For the entire collection see [Zbl 0918.00032].