Is there some known relationship between the connectivity $\kappa(G)$ and the clique number $\omega(G)$ of a graph? Just out of curiosity.

In particular, is $\omega(G)$ bounded by some function of $\kappa(G)$? For instance, $\omega(G) \geq f(\kappa(G))$ for some $f$.

If not, as I believe, is there some known construction of graphs with fixed clique number $\omega$ but arbitrarily high connectivity?

  • 2
    $\begingroup$ $\omega(K_{n,n})=2,$ right? What is $\kappa(K_{n,n})$? $\endgroup$ – bof Apr 11 '16 at 4:30

Counter example:

Let $G=K_{n,n,\ldots,n}$ be a $t$-complete partite graph. Then

$$\omega(K_{n,n,\ldots,n})= t$$ and $$\kappa(K_{n,n,\ldots,n})= n$$

If there exist function $f$ such that $f(\kappa(G)) \leq n $, then $$f(t)\leq n$$ For $n=1$ $$f(t)\leq 1$$

Which is trivial result.

Thus there does not exist $1< f(\kappa(G))$, such that $f(\kappa(G))\leq \omega(G)$

  • 1
    $\begingroup$ As simple as that, thank you! $\endgroup$ – Manuel Lafond Apr 11 '16 at 20:43

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.