# On approximating the achromatic number

Guy Kortsarz, Robert Krauthgamer

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

## ملخص

The achromatic number problem is to legally color the vertices of an input graph with the maximum number of colors, denoted &psgr;*, so that every two color classes share at least one edge. This problem is known to be NP-hard. For general graphs we give an algorithm that approximates the achromatic number within ratio of &Ogr;(n -log log n/ log n). This improves over the previously known approximation ratio of &Ogr; (n/Vlog n), due to Chaudhary and Vishwanathan [4]. For graphs of girth at least 5 we give an algorithm with approximation ratio &Ogr;(min{n1/3, V&psgr;*}). This improves over an approximation ratio &Ogr;(V&psgr;*) = &Ogr;(n3/8) for the more restricted case of graphs with girth at least 6, due to Krista and Lorys [13]. We also give the first hardness result for approximating the achromatic number. We show that for every fixed □ > 0 there in no 2 - D approximation algorithm, unless P = NP.

اللغة الأصلية الإنجليزيّة Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms 309-318 10 نُشِر - 2001 2001 Operating Section Proceedings, American Gas Association - Dallas, TX, الولايات المتّحدةالمدة: ٣٠ أبريل ٢٠٠١ → ١ مايو ٢٠٠١

### سلسلة المنشورات

الاسم Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

### !!Conference

!!Conference 2001 Operating Section Proceedings, American Gas Association الولايات المتّحدة Dallas, TX ٣٠/٠٤/٠١ → ١/٠٥/٠١

## بصمة

أدرس بدقة موضوعات البحث “On approximating the achromatic number'. فهما يشكلان معًا بصمة فريدة.