Chromatic number of a graph with no 4 cycles. 
Suppose $G$ is graph with no $4$-cycles. Let $n$ be the number of vertices of $G$. How can I show that the chromatic number of $G$ is $O(\sqrt{n})$?

The analogous fact about $3$-cycles is well-known.
 A: Let the graph $G$ have $n$ vertices with degrees $d_1, d_2, \dots, d_n$ and average degree $d = \frac1n(d_1 + \dots + d_n)$. We will first show that if $G$ is $C_4$-free, then $d$ cannot be too large, then show that this means $G$ has a large independent set, then iterate to show that $G$ has a small chromatic number. (If this strategy sounds workable, try it for yourself.)
For the first step, we begin by relating the number of 3-vertex paths in $G$ to the average degree $d$. To choose a path on 3 vertices in $G$, we choose a middle vertex $v$, and then choose two of its neighbors $w_1, w_2$. This can be done in $$\sum_{i=1}^n \binom{d_i}{2} \ge n \binom{d}{2}$$ ways, where the inequality follows by convexity of $f(x) = \binom x2$.
If there are more than $\binom n2$ such paths, then by pigeonhole two of them must have the same endpoints, which would make a 4-cycle. We can't have that, so $n \binom d2 \le \binom n2$, which means $d = O(\sqrt n)$.
This was, by the way, a special case of the Kővári–Sós–Turán theorem.
For the second step, we will pick an independent set by the following strategy: sort the vertices at random, and let $I$ be the set of vertices sorted before their neighbors. Then $I$ is an independent set, and the probability that a vertex with degree $d_i$ ends up in $I$ is $\frac1{d_i + 1}$. So the expected number of vertices in $I$ is $$\sum_{i=1}^n \frac1{d_i + 1} \ge \frac n{d+1}$$ where the inequality follows by convexity of $f(x) = \frac1{x+1}$. There must be an independent set of size at least this expected value, and in our case, $\frac n{d+1} = \Omega(\sqrt n)$.
This was, by the way, one of the versions of Turán's theorem, though that's usually stated for cliques and not independent sets.
Finally, we can color the graph $G$ greedily: pick out the largest independent set $I$, give it a color, and repeat this for $G-I$. The remaining graph is also $C_4$-free, so the same argument applies to it, and coloring square-root many vertices at each step colors the entire graph in $O(\sqrt n)$ steps.
