An improved approximation of the achromatic number on bipartite graphs

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The achromatic number of a graph G = (V, E) with |V| = n vertices is the largest number k with the following property: the vertices of G can be partitioned into k independent subsets {Vi}1≤i≤k such that for every distinct pair of subsets Vi, Vj in the partition, there is at least one edge in E that connects these subsets. We describe a greedy algorithm that computes the achromatic number of a bipartite graph within a factor of O(n4/5) of the optimal. Prior to our work, the best known approximation factor for this problem was n log log n/ log n as shown by Kortsarz and Krauthgamer [SIAM J. Discrete Math., 14 (2001), pp. 408-422].

Original languageEnglish (US)
Pages (from-to)361-373
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Issue number2
StatePublished - 2007

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


  • Approximation algorithms
  • Coloring of graphs and hypergraphs
  • Graph algorithms

Fingerprint Dive into the research topics of 'An improved approximation of the achromatic number on bipartite graphs'. Together they form a unique fingerprint.

Cite this