Given a graph $G$ with $m$ edges, what is the maximum chromatic number $\chi(G)$ that the graph can have?
My guess is that $\chi(G) \leq r(m)$ where $r(m) := \max\{k\in \mathbb{N}: \frac{k(k-1)}{2} \leq m\}$, but I can't prove this.
(This is motivated by the fact that the largest complete graph you can form with $m$ edges has $r(m)$ points.)
Your guess is correct. Denote $\chi(G)=k$. Then $G$ contains a subgraph with all degrees at least $k$ (proof: if degree of vertex $v$ is less than $k$, then $\chi(G\setminus v)=k$. Indeed, if $\chi(G\setminus v)<k$, color $G\setminus v$ with $k-1$ colors and then extend this coloring to $v$. So, minimal subgraph of $G$ with chromatic number $k$ can not have vertices of degree less than $k$.) Clearly it has at least $k+1$ vertices, thus at least $k(k+1)/2$ edges.
