The problem of computing k-disjoint maximal cliques covering a maximum number of vertices for weakly triangulated graph
Sumana Bandyopadhyay, Rajat Kumar Pal · 2014
In this paper, a problem of a special class of graph is proved to be NP-complete. The problem is to compute k number of vertex disjoint maximal cliques covering a maximum number of vertices of a graph. The precise graph class considered in this paper is weakly triangulated graph; a class of graph belonging to the domain of perfect graph. There exists immense number of applications by solution of the problem in some graph classes, for which it is polynomially computable, such as comparability graph.