An Improved Approximation of the Achromatic Number on Bipartite Graphs

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 $\{V_i\}_{1 \leq i \leq k}$ such that for every distinct pair of subsets $V_i,V_j$ in the partition, there i...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2007-01, Vol.21 (2), p.361-373
Main Authors: Kortsarz, Guy, Shende, Sunil
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 $\{V_i\}_{1 \leq i \leq k}$ such that for every distinct pair of subsets $V_i,V_j$ 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(n^{4/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].
ISSN:0895-4801
1095-7146
DOI:10.1137/S0895480104442947