chromatic number of a graph versus its complement
What can be said about the rate of growth of f(n), defined by
where the minimum is taken over all graphs G on n vertices.
Two observations.
(1) Either G or contains a clique on roughly logn vertices by Ramsey theory, so for some constant .
(2) If G=G(n,1/2) is a random graph, then n/ log n almost surely, so we also have n/log n for some constant .
These bounds seem hopelessly far apart.
Can we improve on the bounds
for all sufficiently large n?