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

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, \ldots, 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\}) \).