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


2 Answers 2


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

  • $\begingroup$ Thanks, Tony! In conjunction with David's remarks, this shows that the chromatic number is $\Theta(\sqrt{k})$. $\endgroup$ May 28, 2014 at 19:51

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.

  • $\begingroup$ Nice lower-bound construction, David! Thanks! $\endgroup$ May 28, 2014 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.