# Connectivity vs clique number of a graph

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?

• $\omega(K_{n,n})=2,$ right? What is $\kappa(K_{n,n})$? – 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)$

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