Maximal-clique partitions

This dissertation discusses maximal-clique partition problems with emphasis on existence problems. We obtain a necessary and sufficient condition for a line graph to have a maximal-clique partition. There are three clique parameters of a graph G: the clique covering number cc( G), the clique partition number cp(G), and the maximal-clique partition number mcp(G). We evaluate all three clique parameters for line graphs. In addition, we discuss the complexity of the problem of finding maximal-clique partitions for line graphs. We then investigate graphs with maximal-clique partitions of different sizes. The graph L(K5) has two maximal-clique partitions of different sizes. We confirm that there are no graphs with maximal-clique partitions of different sizes of fewer vertices than L(K5). Also, for each natural number n, we give a clique-inseparable graph with n maximal-clique partitions of n different sizes. We investigate the question of the existence of a graph G with cc(G) = cp( G) < mcp(G). We achieve infinitely many graphs satisfying this property. Finally, we solve another existence problem regarding graphs with cc(G) < cp(G) < mcp(G). In 1982, Pullman, Shank and Wallis showed a graph of 11 vertices satisfying cc( G) < cp(G) < mcp (G) and asked whether or not there exists a graph of fewer vertices with cc(G) < cp(G) < mcp(G). We confirm that there is no such a graph.