Covering graphs by the minimum number of equivalence relations

An equivalence graph is a vertex disjoint union of complete graphs. For a graph G, let eq(G) be the minimum number of equivalence subgraphs of G needed to cover all edges of G. Similarly, let cc(G) be the minimum number of complete subgraphs of G needed to cover all its edges. Let H be a graph on n vertices with maximal degree ≦d (and minimal degree ≧1), and let G= {Mathematical expression} be its complement. We show that {Mathematical expression} The lower bound is proved by multilinear techniques (exterior algebra), and its assertion for the complement of an n-cycle settles a problem of Frankl. The upper bound is proved by probabilistic arguments, and it generalizes results of de Caen, Gregory and Pullman.