Approximating the Achromatic Number Problem on Bipartite Graphs

The achromatic number of a graph is the largest number of colors needed to legally color the vertices of the graph so that adjacent vertices get different colors and for every pair of distinct colors c₁,c₂ there exists at least one edge whose endpoints are colored by c₁,c ₂. We give a greedy O(n^4/5) ratio approximation for the problem of finding the achromatic number of a bipartite graph with n vertices. The previous best known ratio was n · log log n/log n [12]. We also establish the first non-constant hardness of approximation ratio for the achromatic number problem; in particular, this hardness result also gives the first such result for bipartite graphs. We show that unless NP has a randomized quasi-polynomial algorithm, it is not possible to approximate achromatic number on bipartite graph within a factor of (ln n)^1/4-ε. The methods used for proving the hardness result build upon the combination of one-round, two-provers techniques and zero-knowledge techniques inspired by Feige et.al. [6].