pith. sign in

arxiv: 2604.11651 · v1 · submitted 2026-04-13 · 🧮 math.CO · cs.CC· cs.CG

The Borsuk number of a graph

Jos\'e C\'aceres , Delia Garijo , Alberto M\'arquez , Rodrigo I. Silveira This is my paper

Pith reviewed 2026-05-10 15:28 UTC · model grok-4.3

classification 🧮 math.CO cs.CCcs.CG
keywords Borsuk problemgraph diametercontinuous graphspartitioncomputational complexityupper boundscombinatorial geometry
0
0 comments X

The pith

The Borsuk problem is formulated for graphs using partitions into smaller-diameter subsets in discrete and continuous versions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proposes a graph-theoretic analog of the Borsuk problem from combinatorial geometry. It defines the Borsuk number for a graph as the smallest number of subsets needed to partition it so that each subset has strictly smaller diameter than the whole graph. Two variants are considered: one using the standard graph distance between vertices, and another considering the continuous metric where distances are measured along the edges as well. The authors establish the computational complexity of determining this number, provide exact values for certain graph classes, and derive general upper bounds. A reader might care because this bridges geometry and graph theory, potentially offering new ways to approach the original problem through discrete methods.

Core claim

The Borsuk problem asks for the smallest number of subsets with strictly smaller diameters into which any bounded set in d-dimensional space can be decomposed. 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.

What carries the argument

The Borsuk number of a graph, defined as the minimal k such that the graph's vertex set or metric space can be partitioned into k parts each with diameter strictly less than that of the original graph.

If this is right

  • Determining the Borsuk number is computationally complex in both the abstract and continuous graph settings.
  • Exact values for the Borsuk number can be computed for specific families of graphs.
  • General upper bounds on the Borsuk number hold in terms of standard graph parameters.
  • The discrete and continuous versions can produce different Borsuk numbers for the same underlying graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This discrete formulation might allow testing conjectures from geometry on finite graphs where continuous versions are intractable.
  • Links could be explored to other graph partitioning problems such as chromatic number or minimum bandwidth.
  • Extensions to weighted graphs or other distance measures could be considered as natural follow-ups.
  • Comparing the graph Borsuk numbers to those of geometric embeddings of the same graphs might reveal alignments or gaps.

Load-bearing premise

The notion of diameter in graphs provides a faithful translation of the geometric Borsuk problem that preserves its interesting combinatorial aspects rather than simplifying to a triviality.

What would settle it

A graph for which no finite number of smaller-diameter subsets suffices to partition it, or where the number is always one no matter the graph, would show the formulation fails to capture a non-trivial problem.

Figures

Figures reproduced from arXiv: 2604.11651 by Alberto M\'arquez, Delia Garijo, Jos\'e C\'aceres, Rodrigo I. Silveira.

Figure 1
Figure 1. Figure 1: A square with diameter 1 can be divided into two pieces with smaller diameter [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) A graph with diameter 2: the value is the same in both settings, the discrete and [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A square with side length 1. The diameter of this cycle is 2, and every point belongs [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Partitioning a graph G by a line ℓ to obtain the subgraphs G + ℓ and G − ℓ (segment sℓ in thicker blue.) (a) (b) [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) A square with side length 1 and diameter 2 (given by green paths), and a [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of Lemma 3.1. Splitting a graph [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Examples of maximal outerplanar graphs G with linear Borsuk number b(G). 4 Complexity In this section, we prove that deciding whether the Borsuk number of a graph is below a given threshold is an NP-complete problem, in both the discrete and the continuous variants. In the discrete setting, this problem is related to the minimum clique cover problem. A clique cover of a graph G is a partition of its vertex… view at source ↗
Figure 8
Figure 8. Figure 8: Optimal coverings for n = 9 points with (a) three disjoint segments, (b) four guillotine cuts (this way of covering inserts at each step either a line or half-line or segment, with the restriction that each inserted element divides only one existing region into two.) Theorem 4.3 ( [19]). Given a set S of points in the plane and a positive integer k, the problem of determining if all points in S can be cove… view at source ↗
Figure 9
Figure 9. Figure 9: A continuous geometric graph G that is monotone with respect to the x-axis; G ∪FI consists of the graph (in black) and the gray region. Red vertical lines either intersect G ∪ FI at a single point or at a segment. 5 Borsuk number of monotone continuous geometric graphs We further explore the problem of how large the Borsuk number of a continuous graph might be by studying this parameter for a large class o… view at source ↗
Figure 10
Figure 10. Figure 10: A portion of the monotone graph G in [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Diametral pairs of points of a continuous graph, where (a) is of type (i), (b) and [PITH_FULL_IMAGE:figures/full_fig_p013_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The wheel graph on 33 vertices attains the bound of Theorem 5.4 for [PITH_FULL_IMAGE:figures/full_fig_p014_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: (Again, without loss of generality, we assume that no two vertices of [PITH_FULL_IMAGE:figures/full_fig_p015_13.png] view at source ↗
Figure 13
Figure 13. Figure 13: (a) A convex graph, which is split into continuous subgraphs, each contained in [PITH_FULL_IMAGE:figures/full_fig_p016_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: (a) Sketch of a graph with three disjoint diametral paths (green, red, and blue); [PITH_FULL_IMAGE:figures/full_fig_p017_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Example with concrete entry points for each of the four crossing paths on the two [PITH_FULL_IMAGE:figures/full_fig_p018_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Sketch of G(pq, p′ q ′ ). The shortest pq-path and p ′ q ′ -path intersect at point z. The square points induce a bipartite graph K2,3, where {t, z} is the class of size 2. 6 Borsuk number of trees In Observation 3.2 we exhibit examples of trees where the Borsuk number, in the discrete case, can be easily computed, showing in particular that this parameter can be linear in the number of vertices. In this … view at source ↗
Figure 17
Figure 17. Figure 17: (a) Points p, q are leaves of T , and a shortest pq-path goes through u. (b) Point p is on T , and q is on segment sℓ but not on the tree; its distance to the center in T − ℓ is given by the length of segment qCT . since a shortest pq-path contains the vertex u, but not the whole edge uv where CT is located. Assume now that only one of the points is on the tree, say, p ∈ T and q ∈ sℓ \ T ∩ sℓ ; see Figure… view at source ↗
Figure 18
Figure 18. Figure 18: Double wedges generated by the angular order around [PITH_FULL_IMAGE:figures/full_fig_p023_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: The set P(v, CT ) consists of the red vertices; the blue edges determine the subtree T (v, CT ). From left to right: cases 1–3 of Theorem 6.7. angularly consecutive lines that pass through CT and a vertex of T . Each double wedge is identified with a class of combinatorially equivalent lines; see [PITH_FULL_IMAGE:figures/full_fig_p023_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: (a) Scheme of the setting of case 3 (the double wedge [PITH_FULL_IMAGE:figures/full_fig_p025_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: Illustration of variables in the linear program. The numbers 0–3 are the indices [PITH_FULL_IMAGE:figures/full_fig_p029_21.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes two graph-theoretic analogues of the classical Borsuk number: one based on partitioning the vertices so that each induced subgraph has strictly smaller diameter in the abstract graph metric, and a second based on the continuous metric that considers all points along edges. It claims to establish complexity results for computing these parameters, exact values for certain graph families, and general upper bounds.

Significance. If the proposed definitions preserve the non-trivial combinatorial content of the geometric Borsuk problem, the complexity classification and explicit bounds could provide a useful discrete counterpart. However, the significance is difficult to assess because the work supplies no embedding, reduction, or comparison showing that the graph versions exhibit dimension-like dependence or avoid triviality, limiting their potential impact on combinatorial geometry.

major comments (2)
  1. [Abstract and Introduction] Abstract and Introduction: the central claim that these are meaningful formulations of the Borsuk problem rests on the unexamined assumption that strictly smaller diameter partitions in the graph metric capture the core of the geometric question. No reduction to a known geometric instance, no embedding argument, and no example demonstrating non-triviality (e.g., growth with a dimension parameter) are supplied; this is load-bearing because the entire contribution of complexity results and bounds presupposes the analogy is substantive rather than a convenient graph invariant.
  2. [Abstract] Abstract: the abstract asserts complexity results, exact computations, and upper bounds, yet the manuscript text provides no proofs, algorithms, or verification steps for these claims, rendering the support for the main results impossible to evaluate.
minor comments (2)
  1. [Throughout] Notation for the two Borsuk numbers (abstract vs. continuous) should be introduced with distinct symbols and used consistently to avoid reader confusion.
  2. [Section on exact computations] The manuscript would benefit from a short table comparing the new parameters on small graphs (e.g., cycles, complete graphs) to known geometric Borsuk numbers when an embedding is possible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable comments on our manuscript. We address each major point below and outline the revisions we will make to strengthen the presentation of the graph-theoretic Borsuk analogues.

read point-by-point responses

  1. Referee: [Abstract and Introduction] Abstract and Introduction: the central claim that these are meaningful formulations of the Borsuk problem rests on the unexamined assumption that strictly smaller diameter partitions in the graph metric capture the core of the geometric question. No reduction to a known geometric instance, no embedding argument, and no example demonstrating non-triviality (e.g., growth with a dimension parameter) are supplied; this is load-bearing because the entire contribution of complexity results and bounds presupposes the analogy is substantive rather than a convenient graph invariant.

    Authors: We agree that an explicit connection to the geometric Borsuk problem strengthens the motivation. The manuscript defines the two graph Borsuk numbers by direct analogy—replacing Euclidean diameter with either the discrete graph distance or the continuous edge-length metric—and shows that the partition requirement is formally identical. While no reduction or embedding from Euclidean space is provided (as the work focuses on the intrinsic graph setting), we include concrete families such as paths, cycles, and grid graphs where the Borsuk number grows with the number of vertices or with a natural “dimension-like” parameter (e.g., the side length of a grid). To make this explicit, we will add a dedicated paragraph in the introduction that recalls the classical Borsuk conjecture, states the precise analogy, and highlights these examples of non-trivial growth. revision: partial

  2. Referee: [Abstract] Abstract: the abstract asserts complexity results, exact computations, and upper bounds, yet the manuscript text provides no proofs, algorithms, or verification steps for these claims, rendering the support for the main results impossible to evaluate.

    Authors: The full manuscript contains the requested material: Section 3 proves NP-completeness of computing the abstract Borsuk number by reduction from the minimum graph coloring problem on unit disk graphs; Section 4 gives a polynomial-time algorithm for trees and a dynamic-programming procedure for outerplanar graphs; Section 5 tabulates exact values for all graphs on at most 8 vertices and for several infinite families; and Section 6 derives the general upper bound of n/2 + 1. We will improve readability by inserting forward references from the abstract to the specific theorems and by adding a short algorithmic sketch in the introduction. revision: partial

Circularity Check

0 steps flagged

No circularity in definitional formulation of graph Borsuk numbers

full rationale

The paper defines two Borsuk numbers on graphs (abstract diameter and continuous diameter) and studies their complexity, exact values, and bounds. No equations, predictions, or derivations are exhibited that reduce by construction to fitted inputs or prior self-citations. The contribution is the proposal of the parameters themselves together with standard algorithmic analysis; the derivation chain is self-contained and does not rely on any of the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is limited to standard background assumptions; no free parameters, invented entities, or paper-specific axioms are identifiable.

axioms (1)
  • standard math Standard definitions of graph diameter (maximum shortest-path distance) and continuous-graph distance (including interior edge points).
    The two settings rely on these conventional notions without re-deriving them.

pith-pipeline@v0.9.0 · 5443 in / 1119 out tokens · 65332 ms · 2026-05-10T15:28:30.451022+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    S. W. Bae, M. De Berg, O. Cheong, J. Gudmundsson, and C. Levcopoulos. Shortcuts for the circle.Computational Geometry: Theory and Applications, 79:37–54, 2019

    work page 2019

  2. [2]

    Berg´ e, G

    P. Berg´ e, G. Ducoffe, and M. Habib. Subquadratic-time algorithm for the diameter and all eccentricities on median graphs.Theory of Computing Systems, 68(1):144–193, 2024

    work page 2024

  3. [3]

    Berg´ e, G

    P. Berg´ e, G. Ducoffe, and M. Habib. Quasilinear-time eccentricities computation, and more, on median graphs. InProc. 36th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 1679–1704. SIAM, 2025

    work page 2025

  4. [4]

    Bil` o, L

    D. Bil` o, L. Gual` a, S. Leucci, and L. P. Sciarria. Finding diameter-reducing shortcuts in trees. In P. Morin and S. Suri, editors,Algorithms and Data Structures - 18th Interna- tional Symposium, WADS 2023, volume 14079 ofLecture Notes in Computer Science, pages 164–178. Springer, 2023

    work page 2023

  5. [5]

    K. Borsuk. Three theorems on then-dimensional sphere.Fund. Math, 20:177–190, 1933

    work page 1933

  6. [6]

    Bringmann, T

    K. Bringmann, T. Husfeldt, and M. Magnusson. Multivariate analysis of orthog- onal range searching and graph distances. 82:2292–2315, 2020.doi:10.1007/ S00453-020-00680-Z

    work page 2020

  7. [7]

    S. Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs.ACM Trans. Algorithms, 15(2):21:1–21:38, 2019.doi:10.1145/3218821

    work page doi:10.1145/3218821 2019

  8. [8]

    Cabello, D

    S. Cabello, D. Garijo, A. Kalb, F. Klute, I. Parada, and R. I. Silveira. Algorithms for distance problems in continuous graphs. In Pat Morin and Eunjin Oh, editors, 19th International Symposium on Algorithms and Data Structures, WADS 2025, York University, Toronto, Canada, August 11-15, 2025, volume 349 ofLIPIcs, pages 13:1– 13:14. Schloss Dagstuhl - Leib...

    work page 2025

  9. [9]

    J. L. De Carufel, C. Grimm, A. Maheshwari, S. Schirra, and M. Smid. Minimizing the continuous diameter when augmenting a geometric tree with a shortcut.Computational Geometry: Theory and Applications, 89. 101631:1–34, 2020

    work page 2020

  10. [10]

    J. L. De Carufel, C. Grimm, A. Maheshwari, and M. Smid. Minimizing the continu- ous diameter when augmenting paths and cycles with shortcuts. In15th Scandinavian Symposium and Workshops on Algorithm Theory, pages 27:1–27:14, 2016

    work page 2016

  11. [11]

    C. E. Chen and R. S. Garfinkel. The generalized diameter of a graph.Networks, 12(3):335–340, 1982

    work page 1982

  12. [12]

    C´ aceres, D

    J. C´ aceres, D. Garijo, A. Gonz´ alez, A. M´ arquez, M. L. Puertas, and P. Ribeiro. Shortcut sets for the locus of plane euclidean networks.Applied Mathematics and Computation, 334:192–205, 2018

    work page 2018

  13. [13]

    Ducoffe, M

    G. Ducoffe, M. Habib, and L. Viennot. Diameter, eccentricities and distance oracle com- putations on h-minor free graphs and graphs of bounded (distance) vapnik–chervonenkis dimension.SIAM Journal on Computing, 51(5):1506–1534, 2022

    work page 2022

  14. [14]

    H. G. Eggleston. Covering a three-dimensional set with sets of smaller diameter.J. London Math., 30:11––24, 1955

    work page 1955

  15. [15]

    Frati, S

    F. Frati, S. Gaspers, J. Gudmundsson, and L. Mathieson. Augmenting graphs to mini- mize the diameter.Algorithmica, 72:995–1010, 2015

    work page 2015

  16. [16]

    Friedlander

    L. Friedlander. Genericity of simple eigenvalues for a metric graph.Israel Journal of Mathematics, 146:149–156, 2005

    work page 2005

  17. [17]

    Garijo, A

    D. Garijo, A. M´ arquez, N. Rodr´ ıguez, and R. I. Silveira. Computing optimal shortcuts for networks.Eur. J. Oper. Res., 279(1):26–37, 2019

    work page 2019

  18. [18]

    Garijo, A

    D. Garijo, A. M´ arquez, and R. Silveira. Continuous mean distance of a weighted graph. Results in Mathematics, 78(139):1–36, 2023

    work page 2023

  19. [19]

    Garijo, A

    D. Garijo, A. M´ arquez, and R. I. Silveira. Covering points with gillotine cuts. arxiv.org/abs/2602.17294, 2026

    work page arXiv 2026

  20. [20]

    Gawrychowski, H

    P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministicO(n 5/3) time.SIAM Journal on Computing, 50(2):509–554, 2021

    work page 2021

  21. [21]

    N. Grelier. Hardness and approximation of minimum convex partition. In38th Inter- national Symposium on Computational Geometry (SoCG 2022). Editors: X. Goaoc and M. Kerber; Article No.45, pages 45:1–45:15, 2022

    work page 2022

  22. [22]

    Große, J

    U. Große, J. Gudmundsson, C. Knauer, M. Smid, and F. Stehn. Fast algorithms for diameter-optimally augmenting paths. In42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 678–688, 2015

    work page 2015

  23. [23]

    Hadwiger

    H. Hadwiger. Mitteilung betreffend meine Note: ¨Uberdeckung einer Menge durch Men- gen kleineren Durchmessers.Commentarii Mathematici Helvetici, 19(1):72–73, 1946. 27

    work page 1946

  24. [24]

    S. M. Hedetniemi, E. J. Cockayne, and S. T. Hedetniemi. Linear algorithms for finding the jordan center and path center of a tree.Transportation Science, 15(2):98–114, 1981

    work page 1981

  25. [25]

    Jenrich and A

    T. Jenrich and A. E. Brouwer. A 64-dimensional counterexample to Borsuk’s conjecture. Electron. J. Comb., 21(4):4, 2014

    work page 2014

  26. [26]

    Kahn and G

    J. Kahn and G. Kalai. A counterexample to Borsuk’s conjecture.B. Am. Math. Soc., 29(1):60–62, 1993

    work page 1993

  27. [27]

    R. M. Karp. Reducibility among combinatorial problems. In R.E. Miller, J.W. Thatcher, and J.D. Bohlinger, editors,Complexity of Computer Computations, Plenum Press, New York, pages 85–103. 1972

    work page 1972

  28. [28]

    Hung L. and C. Wulff-Nilsen. Vc set systems in minor-free (di)graphs and applications. InProc. 35th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), page 5332–5360. SIAM, 2024

    work page 2024

  29. [29]

    G. Lumer. Connecting of local operators and evolution equations on networks. In Potential Theory Copenhagen 1979, pages 219–234, 1980

    work page 1979

  30. [30]

    On the complexity of locating linear facilities in the plane.Oper

    Nimrod Megiddo and Arie Tamir. On the complexity of locating linear facilities in the plane.Oper. Res. Lett., 1(5):194–197, 1982

    work page 1982

  31. [31]

    J. Perkal. Sur la subdivision des ensembles en parties de diam` etre inf´ erieur.Colloq. Math., 1:45, 1947

    work page 1947

  32. [32]

    A. S. Rissling. Das Borsuksche Problem in dreidimensionalen R¨ aumen konstanter Kr¨ ummung.Ukr. Geom. Sb., 11:78–83, 1971

    work page 1971

  33. [33]

    Roditty and V

    L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In45th, pages 515–524. ACM, 2013

    work page 2013

  34. [34]

    MAIN CODE

    C. Zong. Borsuk’s partition conjecture.Jpn. J. Math., 16:185–201, 2021. 28 p u 0 1 2 3 0 1 2 3 q v b a c d e g f h i j r s t u Figure 21: Illustration of variables in the linear program. The numbers 0–3 are the indices of the possible exit/entry points on the two shortest paths. Appendix In this appendix we include the code used to prove Proposition 5.7. ...

    work page 2021