On Diameter Graphs Problems: A proof of Brass's Conjecture
Source: arxiv.org/abs/2611.05631
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05631
curl -X POST /api/v1/records/arxiv/2611.05631/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05631/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'