PreprintCC BY-NC-ND 4.0arXiv
On Diameter Graphs Problems: A proof of Brass's Conjecture
Abstract
The diameter graph of a finite set S⊂ℝd has vertex set S and two points are adjacent when their distance equals 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⊂ℝ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⊂ℝ3 in which every subset of smaller diameter has less than $(|S|-m)/2$ points.
Related
- A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs
- A proof of the resistance diameter conjecture for line graphs
- Proof of the Göbel-Veldman conjecture on diametrical graphs
- A Proof of the Tratnik-Ye Medianity Conjecture of Resonance Graphs on Surfaces
- A Complete Proof of the Strong Conjecture about F-Irregular Graphs
BibTeX
@misc{lopezcampos2026diameter,
title = {{On Diameter Graphs Problems: A proof of Brass's Conjecture}},
author = {Gyivan Lopez-Campos},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05631},
eprint = {2611.05631},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05631},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - On Diameter Graphs Problems: A proof of Brass's Conjecture
AU - Gyivan Lopez-Campos
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05631
UR - https://arxiv.org/abs/2611.05631
AB - The diameter graph of a finite set S⊂ℝ^d has vertex set S and two points are adjacent when their distance equals 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⊂ℝ^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⊂ℝ^3 in which every subset of smaller diameter has less than $(|S|-m)/2$ points.
ER -