An Approximation Algorithm for the Achromatic Number of Circulant graphs $(G(n;\pm \{1,2\}),G(n;\pm \{1,2,3\})$

Abstract

The achromatic number for a graph $G=(V,E)$ is the largest integer $m$ such that there is a partition of $V$ into disjoint independent sets $(V_1,\dots ,V_m)$ such that for each pair of distinct sets $V_i,V_j$, $V_i\cup V_j$ is not an independent set in $G$. In this paper, we present an $O(1)$-approximation algorithm to determine the achromatic number of circulant graphs $G(n;\pm \{1,2\})$ and $G(n;\pm \{1,2,3\})$.