Bounds on chromatic number of $k$-planar graphs

Question

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})$.

Answer 1

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)$.

Answer 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.