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

  • $\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 at 11:24
  • $\begingroup$ Do we know the same question on Planar + 1e (a graph obtained from a planar graph by adding one edge)? $\endgroup$ – Yixin Cao yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.