I am trying to prove that there is some $c>0$ such that $r_k(C_4)\geq k^{1+c}$, where $r_k(C_4)$ is the smallest n such that a k-colouring of $K_k$ contains a monocromatic $C_4$.
I used many ways, incluing taking a $K_{k^2}$, a vertex $v \in V(K_{k^2})$ and start deleting every vertice where $d(u)\geq k+1$, where $u$ and $v$ are neighbor, but didnt worked.
Could someone give me a hand?
Consider starting by trying to color a complete bipartite graph $K_{n,n}$ without getting a monochromatic $C_4$ (or in other words $K_{2,2}$).
This is isomorphic to the problem of coloring a square grid without getting a rectangle whose four corners are the same color. As shown in my answer to the linked question, this can be done with $O(\sqrt n)$ colors, but maybe there is a simpler construction if we are less greedy.
We can write $K_{2n}$ as the union of $O(\log n)$ overlapping copies of $K_{n,n}$. If we use $k$ separate colors on each of those copies (taking any color we like in cases where edges overlap) then we get a coloring of $K_{2n}$ with $O(k \log n)$ colors, and no monochromatic $C_4$.