An *edge clique cover* of an undirected graph $G$ is a set of cliques of $G$ such that every edge of $G$ is an edge in at least one clique in the set. The *edge clique cover number* $\theta(G)$ is the minimum number of cliques in an edge clique cover of $G$. Equivalently, this is the [intersection number](http://en.wikipedia.org/wiki/Intersection_number_(graph_theory)).


Erdös, Goodman, and Posa [1] have shown that $\theta(G) \leq \lfloor n^2/4 \rfloor$. Moreover, there is a covering with $\lfloor n^2/4 \rfloor$ edges and triangles. For interval graphs, $\theta(G)$ equals the number of maximal cliques of $G$ (minus the number of isolated vertices of $G$) [2].


Are there tighter upper bounds known for other special classes of graphs? There is a survey by Fred Roberts [3], which states: "... there has recently been a large amount of work on these coverings, much of which is in widely scattered places in the literature. It is remarkable how similar these widely scattered results are." The survey is from 1985, and I don't see it mentioning results for classes other than interval graphs. Maybe there are newer developments (that don't cite the survey, and thus I'm not finding them)?




---


[1] [Erdos, Paul, Adolph W. Goodman, and Lajos Pósa. "The representation of a graph by set intersections." Canad. J. Math 18.106-112 (1966): 86.](http://www.math.uri.edu/~eaton/Two.pdf)


[2] Opsut, Robert J., and Fred S. Roberts. "On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems." The theory and applications of graphs (1981): 479-492.


[3] [Roberts, Fred S. "Applications of edge coverings by cliques." Discrete applied mathematics 10.1 (1985): 93-109.](http://www.sciencedirect.com/science/article/pii/0166218X85900617)



Upper bounds on the edge clique cover number on special graph classes
The 1995 paper "A Survey of Clique and Biclique Coverings and Factorizations of (0,1)-Matrices" by Sylvia D. Monson, Norman J. Pullman and Rolf Rees in Bulletin of the ICA, Vulume 14, 17-86, might contain results related to your question. If you cannot find the paper, please send me a note and I can email you a scanned copy.


