The Borsuk number of a graph
This work extends a classical combinatorial geometry problem to graph theory, offering new theoretical insights and computational results for graph partitioning problems.
The authors introduce a graph-theoretic formulation of the Borsuk problem, defining two variants based on vertex-only or continuous-edge diameters. They provide complexity results, exact values, and upper bounds for these parameters.
The Borsuk problem asks for the smallest number of subsets with strictly smaller diameters into which any bounded set in the $d$-dimensional space can be decomposed. It is a classical problem in combinatorial geometry that has been subject of much attention over the years, and research on variants of the problem continues nowadays in a plethora of directions. In this work, we propose a formulation of the problem in the context of graphs. Depending on how the graph is partitioned, we consider two different settings dealing either with the usual notion of diameter in abstract graphs, or with the diameter in the context of continuous graphs, where all points along the edges, instead of only the vertices, must be taken into account when computing distances. We present complexity results, exact computations and upper bounds on the parameters associated to the problem.