0
$\begingroup$

Given a simple oriented graph $G$, let $\theta(G)$ be the clique covering number of G (i.e. the minimum number of cliques needed to cover the vertices of G) and $m(G)$ be the number of maximal cliques of $G$. For example, for the 5-cycle $C_5$, $\theta(C_5) = 3$ and $m(C_5) = 5$ (since there are 5 2-cliques).

Given a graph G, why does $\theta(G) \leq m(G)$ ? (equality for every induced graph is the definition of trivially perfect graphs).

Should be trivial, but I'm missing something.

$\endgroup$
0
$\begingroup$

Every vertex belongs to a maximal clique. By taking the set of all maximal cliques you cover all the vertices (e.g. all $2$-cliques from your example), so $m(G)\geq\theta(G)$.

$\endgroup$
1
  • $\begingroup$ I just realize that my misunderstanding came from the fact that I considered only disjoint clique cover. But I think that the upper bound is the same for "disjoint clique cover number", since every clique is contained in a maximal clique $\endgroup$
    – Greg82
    Oct 29 '18 at 9:27

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.