Restricted greedy clique decompositions and greedy clique decompositions of \(K_ 4\)-free graphs
Let \(p\geq 3\). Consider a clique decomposition of a graph on \(n\) vertices obtained by removing first maximal cliques of order at least \(p\) one by one until none remain, then the other edges are removed one by one. The paper shows that the number of cliques in such a decomposition is at most the number of edges in the Turán graph of order \(n\) with no complete subgraph of order \(p\). (By clique decomposition of a graph a partition of its edge set into cliques is meant).
scientific article; zbMATH DE number 700954