Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 8 down vote accepted

Pach and Toth 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.

share|improve this answer
    
Thanks, Tony! In conjunction with David's remarks, this shows that the chromatic number is $\Theta(\sqrt{k})$. –  Joseph O'Rourke May 28 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.

share|improve this answer
    
Nice lower-bound construction, David! Thanks! –  Joseph O'Rourke May 28 at 19:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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