2
$\begingroup$

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

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

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Juho
    Commented Feb 18, 2015 at 13:17
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .