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,...

  • 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$ 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


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.