Abstract

We establish the complexity of recognizing $A$-distance graphs and estimating the chromatic number of the real line with a set of forbidden distances $A$, where the set $A$ is a collection of elements of a geometric progression with the common ratio equal to a rational number raised to a rational power. For all sets $A$ of this type we have found the chromatic number of the real line with this set of forbidden distances and proved whether the problem of recognizing nonstrictly noninjectively $A$-embeddable-in-$ℝ$ graphs is polynomial or NP-hard.

Keywords

Mathematical Subject Classification

Milestones

Authors