RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2024 Volume 115, Issue 5, Pages 772–781 (Mi mzm14138)

Complexity of Recognizing Multidistance Graphs in $\mathbb{R}^d$

G. M. Sokolov


Abstract: We study the complexity of recognizing $A$-distance graphs in $\mathbb{R}^d$ and prove that for all finite sets $A$ such that any two elements of the set differ by a factor $\geqslant 2$, the recognition problem for $A$-distance graphs is $\mathrm{NP}$-hard for any $d \geqslant 3$.

Keywords: distance graph, chromatic number, graph recognition.

UDC: 519.65

MSC: 05C12 68Q11

Received: 12.08.2023
Revised: 25.09.2023

DOI: 10.4213/mzm14138


 English version:
Mathematical Notes, 2024, 115:5, 809–816

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024