12
$\begingroup$

A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that every 2-planar graph contains a vertex of degree at most 9 and thus every 2-planar is 10-colorable. On the other hand, $K_7$ is a 2-planar graph. So my question is whether there is a 2-planar graph with chromatic number 8 or 9 or 10? Thanks for pointers!

Note the $K_8$ is not 2-planar!

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Dmitry Karpov announced the proof that $\chi(G)\leqslant 9$, but this is not published yet. You may contact him directly: dvk0 at yandex dot ru $\endgroup$
    – Fedor Petrov
    Nov 22, 2019 at 10:54
  • 3
    $\begingroup$ An earlier discussion of coloring $k$-planar graphs (but not helpful in answering this question) is mathoverflow.net/questions/168440/… $\endgroup$
    – Gerry Myerson
    Nov 22, 2019 at 11:46

0

Reset to default

Your Answer

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