<p>Planar graphs are 4-colorable.
Determining if a planar graph is 3-colorable is NP-Complete.</p>
<p>A graph with a crossing number 1 (graph such that it can be drawn with <span class="math-container">$\le 1$</span> crossing) is 5-colorable.</p>
<p>What is the hardness of determining if a graph with crossing number 1 is 4-colorable? Is that NP-Complete?</p>
<p>One can also can ask similar question for crossing numbers 2,3,... and for genus 1,2,...</p>

CC BY-SA 4.0
2020-11-25T11:24:20.890Z
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?!?
Marzio De Biasi
CC BY-SA 4.0
2020-12-01T03:26:29.123Z
Do we know the same question on Planar + 1e (a graph obtained from a planar graph by adding one edge)?
Yixin Cao
<graph-algorithms><np-complete><graph-colouring><complexity>
Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?
William Gasarch
# Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?

(Asked by: username_0 on 2020-11-19)

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

**Tags:** graph-algorithms, np-complete, graph-colouring, complexity
> **Comments:**
> **username_1**: 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?!?  
> **username_2**: Do we know the same question on Planar + 1e (a graph obtained from a planar graph by adding one edge)?  

---

## 0 answers

