3
$\begingroup$

An edge clique cover of an undirected graph $G$ is a set of cliques such that every edge of $G$ belongs to some clique in the set. The edge clique cover number $\theta(G)$ is the minimum size of edge clique cover of $G$.

Let's define $k$-restricted edge clique cover of $G$ as a set of cliques such that every edge of $G$ belongs to at least one but not more the $k$ cliques in the set. The $k$-restricted edge clique cover number $\theta_k(G)$ is the minimum size of $k$-restricted edge clique cover of $G$.

My questions are following: is anything known about this concept? I'm most interested in upper bound on $\theta_k(G)$ in terms of $\theta(G)$, but any reference would help.

$\endgroup$
4
$\begingroup$

In general there can be a rather large difference in these quantities. If you take $k = 1$ you are considering the clique partition vs. clique covering problem. This is studied in Clique partitions and clique coverings by Erdős, Faudree, and Ordman. In Example 1 they construct a graph $G$ on $n$ vertices such that (in your notation) $\theta_1(G)/\theta(G) > n^2 /64.$ In Proposition 1 it is shown that for a graph $G$ on $n$ vertices $\theta_1(G)/\theta(G) \leq n^2/12$ provided $n$ is large. Finding an optimal constant here appears to be an open problem. See Problem (66) in Chung's Open problems of Paul Erdős in graph theory.

I am unaware of work on values of $k > 1,$ but perhaps some of the constructions in the linked paper can be applied to these cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.