8
$\begingroup$

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

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

$\endgroup$
10
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, Tony! In conjunction with David's remarks, this shows that the chromatic number is $\Theta(\sqrt{k})$. $\endgroup$ – Joseph O'Rourke May 28 '14 at 19:51
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice lower-bound construction, David! Thanks! $\endgroup$ – Joseph O'Rourke May 28 '14 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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