Chromatic number with several forbidden distances in the space with the \(\ell_q\)-metric (Q1687983): Difference between revisions

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\).