# Upper bounds on the edge clique cover number on special graph classes

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.

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)?

[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.

• Indeed this is pretty nice. To anyone curious: it is more much more comprehensive than the survey by Fred Roberts. To my specific question, it does contain some upper bounds for special graphs, like $k$-regular graphs and Cartesian products of graphs. – Juho Feb 18 '15 at 13:17
Another good reference is this Master's thesis of Michael Cavers. Among the results presented are bounds for the clique covering number of graphs which are complements of graphs with very few edges. For example, the question of the clique covering number of $K_{2n}$ minus a perfect matching was posed by Orlin and essentially solved by Gregory and Pullman.