Return to Answer

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.

For $k=3$, even better upper bound is known: $|E(G)| \leq 5.5(|V(G)|-2)$ (Pach, Radoicic, Tardos, Toth 2006)

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

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.

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.

For $k=3$, even better upper bound is known: $|E(G)| \leq 5.5(|V(G)|-2)$ (Pach, Radoicic, Tardos, Toth 2006)

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.

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.