Clique number of union.

Question

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?

Regards.

Answer 1

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)$.