# MPI-I-98-1-016

## New approximation algorithms for the achromatic number

### Krysta, Piotr and Lory\'{s}, Krzysztof

**MPI-I-98-1-016**. June** **1998, 26 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

The achromatic number of a graph is the greatest number of colors in a

coloring of the vertices of the graph 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.

The problem of computing this number is NP-complete for general graphs

as proved by Yannakakis and Gavril 1980. The problem is also NP-complete

for trees, that was proved by Cairnie and Edwards 1997.

Chaudhary and Vishwanathan 1997 gave recently a $7$-approximation

algorithm for this problem on trees, and an $O(\sqrt{n})$-approximation

algorithm for the problem on

graphs with girth (length of the shortest cycle) at least six.

We present the first $2$-approximation algorithm for the problem on trees.

This is a new algorithm based on different ideas than one by Chaudhary and

Vishwanathan 1997.

We then give a $1.15$-approximation algorithm for the problem on binary trees and a

$1.58$-approximation for the problem on trees of constant degree. We show that

the algorithms for constant degree trees can be implemented in linear time.

We also present the first $O(n^{3/8})$-approximation algorithm for the problem

on graphs with girth at least six.

Our algorithms are based on an interesting tree partitioning technique.

Moreover, we improve the lower bound of Farber {\em et al.} 1986

for the achromatic number of trees with degree bounded by three.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 841 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-016

**BibTeX**
`@TECHREPORT{``KrystaLorys98-1-016``,`

` AUTHOR = {Krysta, Piotr and Lory\'{s}, Krzysztof},`

` TITLE = {New approximation algorithms for the achromatic number},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-98-1-016},`

` MONTH = {June},`

` YEAR = {1998},`

` ISSN = {0946-011X},`

`}`