Efficient approximation algorithms for the achromatic number

The achromatic number problem is, given a graph G=(V,E), to find the greatest number of colors, Ψ(G), in a coloring of the vertices of G such that adjacent vertices get distinct colors and for every pair of colors some vertex of the first color and some vertex of the second color are adjacent. This problem is NP-complete even for trees. We obtain the following new results using combinatorial approaches to the problem.(1)A polynomial time O(|V|3/8)-approximation algorithm for the problem on graphs with girth at least six.(2)A polynomial time 2-approximation algorithm for the problem on trees. This is an improvement over the best previous 7-approximation algorithm.(3)A linear time asymptotic 1.414-approximation algorithm for the problem when graph G is a tree with maximum degree d(|V|), where d:N⟶N, such that d(|V|)=O(Ψ(G)). For example, d(|V|)=Θ(1) or d(|V|)=Θ(log|V|).(4)A linear time asymptotic 1.118-approximation algorithm for binary trees.We also improve the lower bound on the achromatic number of binary trees.