Difference between Chromatic Number and Clique Number Let $G=(V,E)$ be any graph with $|V|=n$ vertices. 
It is known that $\chi \ge \omega$, where $\chi$ (resp., $\omega$) is the chromatic (resp., clique) number of $G$.
There are several examples (e.g., the Mycielskian) that show that $\chi - \omega$ can be made arbitrarily large. However, in all such examples this difference seems to grow very slowly (i.e., logarithmically) with the number of vertices $n$.
Is this is always the case? Are there graphs for which the difference between the chromatic number and the clique number can be made, say, of the order $n^a$, for some $a>0$?
 A: Yes; in fact, for most graphs, the difference is very large.
Consider the random graph on $n$ vertices: for every edge, we flip an independent fair coin to determine if that edge is present or not.
Then for large $n$, the clique number is almost always close to $2\log_2 n$. Proving that it is actually often this high is tricky, so I'll just prove that it usually does not go higher.
The probability that a set of $k$ vertices forms a clique is $2^{-\binom k2}$, and there are $\binom nk$ sets of $k$ vertices, so the expected number of cliques of order $k$ is $\binom nk 2^{-\binom k2}$, which is very approximately $n^k 2^{-k^2/2}$. When we set $k = 2\log_2 n$, $n^k 2^{-k^2/2} = 1$, and the actual expected number of cliques (without the approximation) is going to $0$ as $n \to \infty$. This means that the probability of having even a single clique on more than $2\log_2 n$ vertices is also going to $0$ as $n \to \infty$.
Meanwhile, there is a different obstacle to having a small chromatic number: the inequality $\chi(G) \ge \frac{n}{\alpha(G)}$, where $\alpha(G)$ is the independence number of $G$. By the same argument as for cliques, the largest independent set in $G$ (the largest set of vertices with no edges between them) also almost never exceeds $2 \log_2 n$. Well, in a proper coloring of $G$, every color must induce an independent set. Therefore for almost all $G$, no color has more than $2\log_2 n$ vertices, and therefore at least $\frac{n}{2\log_2 n}$ colors are needed.
(This is actually a good estimate of the chromatic number of the random graph but, again, the reverse bound is very hard to prove; it was shown by Bollobás in 1988.)
So with probability close to $1$ for a random graph, and therefore for almost all $n$-vertex graphs, the clique number and chromatic number are very far apart: the former is less than $2\log_2 n$ and the latter is more than $\frac{n}{2\log_2 n}$.
