Approximation Algorithms for the Achromatic Number

the greatest number of colors 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 notion has been introduced in 1967 by Harary et al. in a context of
graph homomorphism. The problem is NP-complete even for trees.

In this talk I will review our previous results for the problem and will
present new results. In particular, the following:

A polynomial time O(|V|^{3/8})-approximation algorithm for the
problem on graphs with girth at least six. This improves the best
previously known O(|V|^{1/2})-approximation algorithm.

A polynomial time 2-approximation algorithm for the problem on trees.
This is an improvement over the best previous 7-approximation
algorithm.

NEW: A linear time asymptotic 1.582-approximation algorithm for the
problem on trees of maximum degree bounded by some increasing function
d(|V|). A linear time asymptotic 1.155-approximation algorithm for
binary trees. These two algorithms are based on a different
combinatorial approach to the problem.


Our algorithms are based on tree partitioning techniques. We also improve the
lower bound of Farber et al. for the achromatic number of trees with
maximum degree bounded by three.

This paper is a joint work with Krzysztof Lorys, University of Wroclaw,
Poland.