THE DIFFERENCE BETWEEN THE CLIQUE NUMBERS OF A GRAPH
Louis Caccetta, Paul L. Erdos · 1985
Let G be a simple graph. Its clique covering (partition) number cc(G) (cp(G)) is the least number of complete subgraphs needed to cover (partition) its edge-set. We study the function o(G) cp(G)- cc(G) of graphs G. l. Introduction and Summary Let G be a simple graph on n? 1 vertices. The clique partition [covering] number co(G) [cc(G)] is the least number of cliques (complete subgraphs of G) needed to partition [cover] the edge-set of G. Evidently