10
$\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,...

$\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 '20 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 '20 at 3:26

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.