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