Download this article
Download this article For screen
For printing
Recent Issues
Volume 13, Issue 4
Volume 13, Issue 3
Volume 13, Issue 2
Volume 13, Issue 1
Volume 12, Issue 4
Volume 12, Issue 3
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 4
Volume 11, Issue 3
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 4
Volume 10, Issue 3
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 4
Volume 9, Issue 3
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
Older Issues
Volume 7, Issue 4
Volume 7, Issue 3
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 4
Volume 6, Issue 2-3
Volume 6, Issue 1
Volume 5, Issue 4
Volume 5, Issue 3
Volume 5, Issue 1-2
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 3-4
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 4
Volume 1, Issue 3
Volume 1, Issue 2
Volume 1, Issue 1
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
founded and published with the
scientific support and advice of
mathematicians from the
Moscow Institute of
Physics and Technology
Subscriptions
 
ISSN 2996-220X (online)
ISSN 2996-2196 (print)
Author Index
To Appear
 
Other MSP Journals
This article is available for purchase or by subscription. See below.
Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs

Georgy Sokolov
Vol. 12 (2023), No. 3, 247–258
DOI: 10.2140/moscow.2023.12.247
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.

PDF Access Denied

We have not been able to recognize your IP address 35.173.48.18 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

Keywords
distance graph, chromatic number, computation complexity
Mathematical Subject Classification
Primary: 05C15, 68Q17
Milestones
Received: 7 July 2023
Accepted: 7 August 2023
Published: 23 September 2023
Authors
Georgy Sokolov
Department of Discrete Mathematics
Moscow Institute of Physics and Technology
Moscow
Russia
© 2023 MSP (Mathematical Sciences Publishers).