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

  • $\begingroup$ FWIW I can't find unit distance graph in graphclasses.org. $\endgroup$ – Peter Taylor May 15 '18 at 11:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Gamow May 15 '18 at 11:28
  • 1
    $\begingroup$ @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. $\endgroup$ – Peter Taylor May 15 '18 at 11:32
  • $\begingroup$ Are you looking for lower and upper bounds for the chromatic number of a Unit Distance Graph? $\endgroup$ – user3483902 May 17 '18 at 19:22
  • $\begingroup$ @user No, I'm not. $\endgroup$ – domotorp May 17 '18 at 19:27

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. 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 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. Using this gadget, $\frac 83$ can play the role of $\sqrt 3$ in the previous construction.

  • $\begingroup$ How would you implement this reduction in polynomial time? Many points will have irrational coordinates. $\endgroup$ – Alexis May 21 '18 at 12:34
  • $\begingroup$ @Alexis We needn't implement it, though I doubt it would be hard. $\endgroup$ – domotorp May 21 '18 at 13:04
  • $\begingroup$ @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... $\endgroup$ – Gamow May 22 '18 at 8:17
  • $\begingroup$ @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. $\endgroup$ – domotorp May 22 '18 at 8:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.