Upper bound relating number of edges of a graph to it's chromatic number

Question

So I am curious if there is an upper bound relating number of edges of a graph to it's chromatic number. More specifically,

Given a graph $G$ where $\chi(G) = k$, then can we deduce an upper bound for the number of edges $G$ must possess ? There are posts that deduce the lower bound, ($k $ choose 2 many).

Cheers

Answer 1

Let $n$ denote the number of nodes and $m$ the number of edges.

Given that (see here) : $$ k \ge \frac{n^2}{n^2-2m} $$ You can derive the following upper bound for $m$ $$ m \le \frac{n^2(k-1)}{2k} $$

Answer 2

Turán's Theorem asserts that the maximum number of edges in an $n$-vertex $K_{k+1}$-free graph is achieved by the Turán graph, which happens to be $k$-colorable. Since all $k$-colorable graphs are $K_{k+1}$-free, the maximum number of edges in an $n$-vertex $k$-colorable graph is also achieved by the Turán graph.

Thus, the number of edges is at most $$\left(1 - \frac{1}{k}\right)\frac{n^2}{2}.$$ An exact formula is given on the Turán graph Wikipedia page which is a bit messy.