2
$\begingroup$

Suppose the independent number of a graph is bounded. How small the clique number can be? linear? It seems to be a natural problem to ask. but I could not find any reference. Thanks.

$\endgroup$

1 Answer 1

10
$\begingroup$

This is basically a question in Ramsey theory. The Ramsey number $R(s, t)$ is the minimum integer $n$ for which every red-blue coloring of the edges of a complete $n$-vertex graph induces either a red complete graph of order $s$ or a blue complete graph of order $t$. So for example Kim (Random Structures and Algorithms 7 (1995), 173-207) showed that $R(3,t)\asymp t^2/\log t$. Roughly speaking this means that a graph with $t^2/\log t$ vertices with independence number at most 2 must have a clique of size $t$. So in this case the clique number grows like the square root of the number of vertices of the graph. I'm not sure what the best known results are in general but this should point you to the right literature.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.