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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .