Clique coverings of graphs V: maximal-clique partitions
Norman J. Pullman, Herbert S. Shank, W. D. Wallis · Bulletin of the Australian Mathematical Society · 1982
A maximal-clique partition of a graph G is a way of covering G with maximal complete subgraphs, such that every edge belongs to exactly one of the subgraphs. If G has a maximal-clique partition, the maximal-clique partition number of G is the smallest cardinality of such partitions. In this paper the existence of maximal-clique partitions is discussed – for example, we explicitly describe all graphs with maximal degree at most four which have maximal-clique partitions - and discuss the maximal-clique partition number and its relationship to other clique covering and partition numbers. The number of different maximal-clique partitions of a given graph is also discussed. Several open problems are presented.