Let $\omega(G)$ denotes clique number of graph $G$.

Let $V(G_{1})=V(G_{2})$

Is there are a formula for $\omega(G_{1}\cup G_{2})$ ?

I thought that it may seem like this:

$\omega(G_{1}\cup G_{2})=\omega(G_{1})+\omega(G_{2})-\omega(G_{1}\cap G_{2})$.

But i was wrong.

Any ideas how to solve it?



There is no formula for it; at least, nothing more straightforward than computing $\omega(G_1\cup G_2)$ separately.

Even restricting our attention to cases where $G_1 \cap G_2$ is the empty graph, there are two extreme cases (and everything between them is also possible):

  • We could have $G_1$ and $G_2$ have completely unrelated cliques and get $\omega(G_1 \cup G_2) = \max\{\omega(G_1), \omega(G_2)\}$.
  • On the other hand, we could take a large clique $K_n$ and partition it into graphs $G_1$ and $G_2$ with $\omega(G_1), \omega(G_2) = O(\log n)$, by a lower bound on Ramsey numbers. In this case, $\omega(G_1 \cup G_2)$ is exponential in $\omega(G_1)$ and $\omega(G_2)$.

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.