9
$\begingroup$

Planar graphs are 4-colorable. Determining if a planar graph is 3-colorable is NP-Complete.

A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable.

What is the hardness of determining if a graph with crossing number 1 is 4-colorable? Is that NP-Complete?

One can also can ask similar question for crossing numbers 2,3,... and for genus 1,2,...

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It seems equivalent to checking if two nodes are "fixed", i.e. in all valid 4-colorings of the graph when the crossing is removed, they are forced to have the same color. Iterate between all pairs of edges $\{e_1, e_2\}$ that determines a crossing, and check if the two vertices of one of the two edges (e.g. $e_1$) are forced to have the same color in all 4-colorings of the graph in which $e_1$ is removed). Perhaps the problem of checking if two nodes of a 4-colourable (planar) graph are forced to have the same color is already studied?!? $\endgroup$
    – Marzio De Biasi
    Nov 25, 2020 at 11:24
  • 1
    $\begingroup$ Do we know the same question on Planar + 1e (a graph obtained from a planar graph by adding one edge)? $\endgroup$
    – Yixin Cao
    Dec 1, 2020 at 3:26

0

Reset to default

Your Answer

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