Approximation Algorithms for the Achromatic Number in Trees

of colors, such that two vertices joined by an edge are colored with
different colors, and for any two different colors used, there is an edge
joining some two vertices colored with these colors. The maximum possible
number of colors is called the achromatic number of the tree.

The notion of an achromatic number of a graph was originally introduced by
Frank Harary at al. in 1967. It is not known whether the problem of the
achromatic number of tree is NP-hard or is in P. Although the people
developed approximation algorithms for it in order to know something about
its complexity.

In the SODA '97 conference Chaudhary and Vishwanathan gave a 7-approximation
algorithm for the problem. We have developed some new approach to the
problem, which allowed us to obtain a new, 2-approximation algorithm. We give
moreover an 1.22-approximation algorithm for binary trees, and an
1.58-approximation algorithm for trees with degree bounded by an (arbitrary
fixed) constant. This is joint work with Krzysztof Lory\'{s} from the Institute
of Computer Science, University of Wroclaw, Poland.

In my talk I will cover some selected things from our results.