Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs

DOI10.2140/moscow.2023.12.247zbMath1521.05048OpenAlexW4386988259MaRDI QIDQ6055514

Georgy Sokolov

Publication date: 29 September 2023

Published in: Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/moscow.2023.12.247

zbMATH Keywords

chromatic numberdistance graphcomputation complexity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Ramsey theory (05D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Colouring the real line
• Colouring prime distance graphs
• On the complexity of H-coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Distance graphs and \(T\)-coloring
• Chromatic number of prime distance graphs
• Graph homomorphisms with infinite targets
• On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
• On the chromatic number of a distance graph associated with a lacunary sequence
• Coloring Distance Graphs and Graphs of Diameters
• Two Erdős problems on lacunary sequences: Chromatic number and Diophantine approximation
• The chromatic number of the plane is at least 5
• On the chromatic number of an infinitesimal plane layer
• All finite sets are Ramsey in the maximum norm
• Distance Graphs Generated by Five Primes (Research)
• Chromatic numbers of Cayley graphs on \(\mathbb Z\) and recurrence

This page was built for publication: Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs