<p>Okay, this seems easy. Below I sketch why it is NP-hard to decide if a unit distance graph has a $3$-coloring. They key observation is that in a $3$-coloring any two vertices $u$ and $v$ at distance $\sqrt 3$ must get the same color if the two vertices at unit distance from them are also present in the graph. With this gadget we can convert the decision problem of the $3$-colorability of any graph $G$ into the decision problem of the $3$-colorability of a unit distance graph $G'$as follows.</p>

<p>Map the vertices of $G$ into the plane such that no two are at unit distance. Connect every two adjacent vertices with a polygonal path that consists of segments of length $\sqrt 3$ and one segment of length $1$. Add the endpoints of the segments to the vertices of $G'$, and also the two vertices at unit distance from the ends of segments of length $\sqrt 3$. Now $G'$ is $3$-colorable if and only if $G$ is $3$-colorable if there are no additional coincidences among the vertices of $G'$ but we can pick the paths in a generic way.</p>

<p>With a little more care, we can also show that the problem remains NP-complete if we restrict it to planar unit distance graphs. For this, we need to use that it is <a href="https://doi.org/10.1016/0304-3975(76)90059-1" rel="nofollow noreferrer">NP-hard to decide whether a planar graph with maximum degree $4$ has a $3$-coloring</a>. We can repeat the previous construction, just if we map the vertices of $G$ far away in the plane, then the respective paths won't cross. (For this reduction, maximum degree $6$ would suffice.)
This also proves that it's NP-hard to decide whether the chromatic number of a <a href="https://en.wikipedia.org/wiki/Penny_graph" rel="nofollow noreferrer">coin graph</a> is $3$ or $4$.</p>

<p>A similar construction also shows that deciding whether a unit distance graph is $4$-colorable is also NP-complete using that <a href="https://arxiv.org/abs/1805.00157" rel="nofollow noreferrer">there is a unit distance graph in whose only $4$-coloring two given vertices at distance $\frac 83$ must get the same color</a>. Using this gadget, $\frac 83$ can play the role of $\sqrt 3$ in the previous construction.</p>

CC BY-SA 4.0
2018-05-21T12:34:44.387Z
How would you implement this reduction in polynomial time? Many points will have irrational coordinates.
Alexis
CC BY-SA 4.0
2018-05-21T13:04:51.623Z
@Alexis We needn't implement it, though I doubt it would be hard.
domotorp
CC BY-SA 4.0
2018-05-22T08:17:52.310Z
@domotorp: Alexis' question indicates a quirk in your "proof".  A polynomial time reduction must be implementable on a Turing machine, with a polynomial bound on the running time. But you are using irrational coordinates...
Gamow
CC BY-SA 4.0
2018-05-22T08:51:12.360Z
@Gamow The question is how you define the problem. Do you have to input a realization of the unit distance graph or just any graph with a promise that it's a unit distance graph? I've considered the latter, but as I wrote, I doubt that the former would be much harder.
domotorp
CC BY-SA 4.0
2018-05-18T07:57:48.023Z
2018-05-18T20:54:34.810Z
2018-05-18T20:54:34.810Z
domotorp
<p>For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?</p>

CC BY-SA 4.0
2018-05-15T11:27:03.837Z
FWIW I can't find *unit distance graph* in graphclasses.org.
Peter Taylor
CC BY-SA 4.0
2018-05-15T11:28:30.143Z
@Peter Taylor: Every vertex is a point in the Euclidean plane. There is an edge, if and only if two points are at Euclidean distance 1.
Gamow
CC BY-SA 4.0
2018-05-15T11:32:05.047Z
@Gamow, thanks, but my point wasn't to ask for a definition. I know what it is, and I can guess why the question is being asked (Polymath 16, perhaps?) My point was to save other people the time of checking it (unless they know a synonym), especially because it always takes me ages to find that site when I want it.
Peter Taylor
CC BY-SA 4.0
2018-05-17T19:22:36.703Z
Are you looking for lower and upper bounds for the chromatic number of a Unit Distance Graph?
user3483902
CC BY-SA 4.0
2018-05-17T19:27:26.793Z
@user No, I'm not.
domotorp
<cc.complexity-theory><graph-theory><np-hardness><planar-graphs>
How hard is it to determine the chromatic number of a unit distance graph?
domotorp
# How hard is it to determine the chromatic number of a unit distance graph?

(Asked by: username_0 on 2018-05-15)

For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?

**Tags:** cc.complexity-theory, graph-theory, np-hardness, planar-graphs
> **Comments:**
> **username_1**: FWIW I can't find *unit distance graph* in graphclasses.org.  
> **username_2**: @Peter Taylor: Every vertex is a point in the Euclidean plane. There is an edge, if and only if two points are at Euclidean distance 1.  
> **username_1**: @Gamow, thanks, but my point wasn't to ask for a definition. I know what it is, and I can guess why the question is being asked (Polymath 16, perhaps?) My point was to save other people the time of checking it (unless they know a synonym), especially because it always takes me ages to find that site when I want it.  
> **username_3**: Are you looking for lower and upper bounds for the chromatic number of a Unit Distance Graph?  
> **username_0**: @user No, I'm not.  

---

## 1 answers

### Answer by username_0 on 2018-05-18. Score: 3 | Accepted answer

Okay, this seems easy. Below I sketch why it is NP-hard to decide if a unit distance graph has a $3$-coloring. They key observation is that in a $3$-coloring any two vertices $u$ and $v$ at distance $\sqrt 3$ must get the same color if the two vertices at unit distance from them are also present in the graph. With this gadget we can convert the decision problem of the $3$-colorability of any graph $G$ into the decision problem of the $3$-colorability of a unit distance graph $G'$as follows.

Map the vertices of $G$ into the plane such that no two are at unit distance. Connect every two adjacent vertices with a polygonal path that consists of segments of length $\sqrt 3$ and one segment of length $1$. Add the endpoints of the segments to the vertices of $G'$, and also the two vertices at unit distance from the ends of segments of length $\sqrt 3$. Now $G'$ is $3$-colorable if and only if $G$ is $3$-colorable if there are no additional coincidences among the vertices of $G'$ but we can pick the paths in a generic way.

With a little more care, we can also show that the problem remains NP-complete if we restrict it to planar unit distance graphs. For this, we need to use that it is [NP-hard to decide whether a planar graph with maximum degree $4$ has a $3$-coloring](https://doi.org/10.1016/0304-3975(76)90059-1). We can repeat the previous construction, just if we map the vertices of $G$ far away in the plane, then the respective paths won't cross. (For this reduction, maximum degree $6$ would suffice.)
This also proves that it's NP-hard to decide whether the chromatic number of a [coin graph](https://en.wikipedia.org/wiki/Penny_graph) is $3$ or $4$.

A similar construction also shows that deciding whether a unit distance graph is $4$-colorable is also NP-complete using that [there is a unit distance graph in whose only $4$-coloring two given vertices at distance $\frac 83$ must get the same color](https://arxiv.org/abs/1805.00157). Using this gadget, $\frac 83$ can play the role of $\sqrt 3$ in the previous construction.

> **Comments:**
> **username_4**: How would you implement this reduction in polynomial time? Many points will have irrational coordinates.  
> **username_0**: @Alexis We needn't implement it, though I doubt it would be hard.  
> **username_2**: @domotorp: Alexis' question indicates a quirk in your "proof".  A polynomial time reduction must be implementable on a Turing machine, with a polynomial bound on the running time. But you are using irrational coordinates...  
> **username_0**: @Gamow The question is how you define the problem. Do you have to input a realization of the unit distance graph or just any graph with a promise that it's a unit distance graph? I've considered the latter, but as I wrote, I doubt that the former would be much harder.  

---

