Bounds on chromatic number of $k$-planar graphs A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times. 
Planar graphs are $4$-colorable, and $1$-planar graphs are $6$-colorable.
($K_6$ is $1$-planar: image below from here.)

 
 
 
 
 
 
 
 



What bounds are known on the colorability of $k$-planar graphs?

This has likely been studied; I just don't know the results. Thanks for pointers!

Answered by Tony Huynh and David Eppstein: The chromatic number of a $k$-planar graph is $\Theta(\sqrt{k})$.
 A: 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.
A: 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)$.
