RESTRICTED GREEDY CLIQUE DECOMPOSITIONS AND GREEDY CLIQUE DECOMPOSITIONS OF K(4)-FREE GRAPHS

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of order n has at most n2/4 cliques. In this paper, we extend this result by showing that for any positive integer p, 3 less-than-or-equal-to p any clique decomposition of a graph of order n obtained by removing maximal cliques of order at least p one by one until none remain, in which case the remaining edges are removed one by one, has at most t(p-1)(n) cliques. Here t(p-1)(n) is the number of edges in the Turan graph of order n, which has no complete subgraphs of order p. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decomposition C of a graph G of order n the sum over the number of vertices in each clique of C is at most n2/2. We prove this conjecture for K4-free graphs and show that in the case of equality for C and G there are only two possibilities: (i) G congruent-to K(n/2,n/2 (ii) G is complete 3-partite, where each part has n/3 vertices. We show that in either case C is completely determined.