Bounds on chromatic number of $k$-planar graphs

Pach and Tóth proved that if $G$ is a $k$-planar graph (with $k \geq 1$), then

$|E(G)| \leq 4.108 \sqrt{k} |V(G)|$.

Thus, every $k$-planar graph has a vertex of degree at most $\lfloor8.216 \sqrt{k}\rfloor$. By induction, it follows that $k$-planar graphs can be coloured with $\lfloor8.216 \sqrt{k}\rfloor+1$ colours.

For $1 \leq k \leq 4$, they prove a better bound of

$|E(G)| \leq (k+3)(|V(G)|-2)$.

Thus, we can do slightly better for small values of $k$. That is, 2-planar graphs are 10-colourable, 3-planar graphs are 12-colourable, and 4-planar graphs are 14-colourable.

For $k=3$, Pach, Radoičic, Tardos, and Tóth proved an even better upper bound of

$|E(G)| \leq 5.5(|V(G)|-2)$.


To complement Tony Huynh's answer, something proportional to $\sqrt k$ is also a lower bound on the chromatic number: there exist $k$-planar graphs that need this many colors. In particular, if one draws a complete graph of $\Theta(\sqrt k)$ vertices by placing the vertices on a circle and drawing the edges as line segments, the resulting drawing will be $k$-planar but the complete graph will require $\Omega(\sqrt k)$ colors.