arXiv:2611.05631v1 Announce Type: new Abstract: The diameter graph of a finite set $S\subset\mathbb{R}^d$ has vertex set $S$ and two points are adjacent when their distance equals $\operatorname{diam} S$. In this paper we study the following question: given $k$ and $d$, is there a constant $c=c(k,d)$ such that from every finite point set $S\subset\mathbb{R}^d$ one can remove at most $c$ points so that the subgraph of the diameter graph induced by the remaining points is $k$-colorable? Brass conjectured that such a constant exists for $d=3$ and $k=3$. We prove this conjecture by showing that at most one point needs to be removed. We also answer a question of Dol'nikov, showing that for every positive integer $m$, there exist a finite point set $S\subset\mathbb{R}^3$ in which every subset of smaller diameter has less than $(|S|-m)/2$ points.
Continue to arXiv Mathematics →You are being forwarded in 6s — stay on this page