On The Clique-Partitioning Problem

We study the problem of clique-partitions. This upper bound is the best possible, given information of just the vertices and the number of edges. Next, we show that there exists an optimal partition in which one of the clique is a maximal clique. Finally, we present two new efficient methods to clique-partition a graph. Since the clique-partitioning of a graph is equivalent to the coloring of the complement of the graph, any coloring algorithm can also be used to clique-partition a graph.