A Graph b-coloring Framework for Data Clustering

The graph b-coloring is an interesting technique that can be applied to various domains. The proper b-coloring problem is the assignment of colors (classes) to the vertices of one graph so that no two adjacent vertices have the same color, and for each color class there exists at least one dominating vertex which is adjacent (dissimilar) to all other color classes. This paper presents a new graph b-coloring framework for clustering heterogeneous objects into groups. A number of cluster validity indices are also reviewed. Such indices can be used for automatically determining the optimal partition. The proposed approach has interesting properties and gives good results on benchmark data set as well as on real medical data set.