Chromatic number with several forbidden distances in the space with the \(\ell_q\)-metric
type: Item
instance of: scholarly article
title: Chromatic number with several forbidden distances in the space with the \(\ell_q\)-metric
zbMATH Open document ID: 1379.05033
author: Alexey V. Berdnikov
published in: Journal of Mathematical Sciences (New York)
publication date: 2018-01-04T00:00:00Z
review text: The chromatic number of a metric space \((X,\rho)\) with forbidden distance sequence \(a\) is the minimal number of colors needed for coloring all points of the set \(X\) so that the distance between any two points of the same color is not equal to any of the numbers in the sequence \(a\). Classical chromatic number on a finite graph \(G=(V,E)\) is the case \(X=V\), \(\rho=\) graph distance between two vertices, and \(a=(1)\). So a valid coloring in this case requires that each node has a different color from its immediate neighbor. If \(a=(1,2)\), for example, then a valid coloring requires that each node has a different color from its neighbors and its neighbors of neighbors. One may ask: given a fix integer \(k\), what is the sequence \(a\) of length \(k\) that produces the maximal chromatic number? This paper gives a lower bound on this quantity for \(X=\mathbb R^n\) and \(\rho\) is the \(\ell_q\)-norm. This generalizes a result of \textit{A. M. Raigorodsky} [Russ. Math. Surv. 56, No. 1, 103--139 (2001; Zbl 1008.54018); translation from Usp. Mat. Nauk 56, No. 1, 107--146 (2001)], who obtained the bound for the case \(q=2\).
reviewed by: Ngoc Mai Tran
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 6822174
zbMATH Keywords: bounded \(d\)-dimensional set
zbMATH Keywords: chromatic number
MaRDI profile type: Publication
full work available at URL: s10958-017-3592-0
OpenAlex ID: W2765806419
cites work: Estimate for the chromatic number of Euclidean space with several forbidden distances
cites work: Estimating the chromatic numbers of Euclidean space by convex minimization methods
cites work: Colorings of the space \(\mathbb R^{n}\) with several forbidden distances
cites work: Borsuk's problem and the chromatic numbers of some metric spaces
cites work: Q3020323
cites work: Chromatic numbers of real and rational spaces with real or rational forbidden distances
cites work: On the chromatic numbers of metric spaces with few forbidden distances
DOI: 10.1007/S10958-017-3592-0
Recommended article: Colorings of the space \(\mathbb R^{n}\) with several forbidden distances
Recommended article: The chromatic number of a space with the metric $ l_q$
Recommended article: On the chromatic number for a set of metric spaces
Recommended article: Estimate for the chromatic number of Euclidean space with several forbidden distances
Recommended article: Yet another species of forbidden-distances chromatic number
Recommended article: A new lower bound for the chromatic number of the rational space
Recommended article: The chromatic number of the space $( {\mathbb R}^n, l_1)$
Recommended article: All finite sets are Ramsey in the maximum norm
Recommended article: Chromatic numbers of real and rational spaces with real or rational forbidden distances
Recommended article: Q5460291
description: scientific article; zbMATH DE number 6822174