Pith. sign in

REVIEW 2 major objections 4 minor 24 references

Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper surveys continuous graphs — graphs whose edges are unit-length intervals — and proves that the 1/2-chromatic number of the complete continuous graph is at most ⌈n/2⌉, supporting a conjecture that continuous coloring uses about…

desk verdict Useful survey, but its only new theorem (Prop 2) is unproved for odd n and there is a false capacity bound in Section 3.1. read the letter →

arxiv 2501.14554 v2 pith:RC2VHMW2 submitted 2025-01-24 math.CO cs.DM

Alexander Grigoriev , Katherine Faulkner This is my paper · ORCID
classification math.COcs.DM MSC 05C1505C6905C83
keywords continuousgraphsmetricr-independentsetr-coverchromaticnumbertreewidthopenproblemscompletegraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Continuous graphs replace each edge of a graph by a unit-length interval, so any point along an edge can serve as a sensor, cover element, or color-class center. This paper argues that this more physical model changes the answers to the classic Independent Set, Vertex Cover, Chromatic Number, and Treewidth problems, and it surveys what is known about their complexity. Its main new technical result is a proof that the complete continuous graph $\Gamma(K_n)$ can be colored with at most $\lceil n/2 \rceil$ balls of radius $1/2$, via one color per edge of a maximum matching plus extra same-colored balls at the $1/4$ and $3/4$ positions on the remaining edges. This gives the upper-bound half of the paper's conjecture that the exact $1/2$-chromatic number of $\Gamma(K_n)$ is $\lceil n/2 \rceil$; the lower bound is left open, in contrast with the $n$ colors required by the combinatorial $K_n$. The paper also poses open problems on planar continuous graphs, approximation, and the $\alpha$--$\beta$ duality for $r$-covers.

What carries the argument

The central object is the continuous graph $\Gamma(G)$, a metric topological space in which every edge is a rectifiable unit interval and distance is the shortest-path concatenation of edge lengths. The machinery is the $r$-ball: $B(p,r)$ is the inclusion-maximal subgraph of points within distance $r$ of $p$. An $(r,c)$-coloring is a cover of $\Gamma$ by $c$ color classes of radius-$r$ balls in which intersecting balls receive distinct colors. The proof of Proposition 2 rests on a specific ball-placement construction: the midpoints of a maximum matching receive distinct colors, and for every pair of matching edges, additional balls of the two matching colors are placed at symmetric $1/4$ and $3/4$ positions on the four crossing edges, with the claimed $1/4$ separation between same-colored balls carrying the disjointness argument.

What would settle it

For a small complete continuous graph such as $\Gamma(K_6)$, compute the shortest-path distances between the centers of every same-coloured pair of balls produced by the Proposition 2 construction. If any such distance is less than $1$, the two radius-$1/2$ balls intersect and the proposed $(1/2,3)$-coloring fails; if all such distances are at least $1$, the upper bound is verified on that instance.

Watch

Extended reading notes

Core claim

In the paper's own terms, the contribution is twofold: it surveys existing algorithmic and hardness results for optimization problems on continuous graphs, and it collects open questions that arise when every edge is a continuum. The one new result proved here is Proposition 2: for every natural $n$, $\chi_{1/2}(\Gamma(K_n)) \le \lceil n/2 \rceil$. The proof constructs a $(1/2, \lceil n/2 \rceil)$-coloring by giving each edge of a maximum matching its own color, then placing additional same-colored balls of radius $1/2$ on the non-matching edges at distances $1/4$ and $3/4$ from the endpoints, asserting that same-colored balls are separated by a gap of $1/4$. The paper explicitly leaves the matching lower bound, and hence the exact $1/2$-chromatic number, as a conjecture.

Load-bearing premise

The upper-bound proof of Proposition 2 stands or falls on the assertion that every pair of same-coloured balls in the constructed cover is disjoint; the text supports this with a separation claim of $1/4$ but does not show the center-to-center distance calculation for every pair, so if any same-coloured pair of balls meets, the construction is not a proper coloring.

Editorial extensions

If this is right

  • If Proposition 2 is correct, the conjectured exact value $\chi_{1/2}(\Gamma(K_n)) = \lceil n/2 \rceil$ needs only a matching lower bound; the upper bound is already in hand.
  • The construction makes the gap between classical and continuous coloring concrete: $K_n$ requires $n$ colors, while its continuous counterpart is colorable with about $n/2$ colors of radius $1/2$.
  • The relaxation-gap example for independent sets ($\alpha_1(\Gamma(K_n)) \ge n/2$ while $\alpha(K_n)=1$) and the $\alpha_1 + \beta_1 = n$ duality for $r=1$ show that continuous problems are not scaled copies of combinatorial ones.
  • The surveyed complexity results — polynomial time for unit-fraction radii and NP-hardness for non-unit-fraction radii — imply that tractability of these continuous problems is governed by the arithmetic of $r$.
  • If the continuous planar graph conjecture is true, every continuous planar graph would be $(1/2,3)$-colorable, one color fewer than the classical planar four-color bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next test is whether the matching-symmetry construction extends to other symmetric continuous graphs, such as complete bipartite graphs, giving a family of upper bounds that would sharpen the picture of the relaxation gap.
  • If the disjointness gap in Proposition 2 is repaired, the obvious next step is a packing or bramble argument for the lower bound; if the gap cannot be repaired, the conjecture could still be true but would need a different construction.
  • The paper's open question about constant-factor approximation for maximum $r$-independent sets suggests a plausible conjecture: for every fixed rational $r$, such an approximation exists, extending the unit-fraction tractability.
  • The continuous planar three-color conjecture, if true, would show that the metric structure of the plane reduces the color count by one relative to the abstract planar case, a phenomenon with no classical analogue.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper surveys four classical graph parameters—maximum independent set, vertex cover, chromatic number, and treewidth—in their "continuous graph" counterparts, where edges are unit-length intervals and feasible points may be placed anywhere on the graph. It restates known results from the literature (notably by Hartmann, Lendl, Woeginger, and Grigoriev et al.), adds a list of open problems, and contributes Proposition 1 and Proposition 2. Proposition 2 gives the upper bound χ_{1/2}(Γ(K_n)) ≤ ⌈n/2⌉ for complete continuous graphs, and the authors conjecture equality.

Significance. If the claims are repaired, the survey would be a useful synthesis of recent work on continuous facility location and graph coloring, and Proposition 2 would be a valuable new upper bound matching a natural conjecture. The literature reporting appears consistent with the cited sources, and the open-problem list is a genuine service to the community. However, two points in the new material currently need repair: the per-edge capacity bound in Section 3.1 is false as stated, and the odd-n case of Proposition 2 is not established by the given reduction. These are local and likely repairable, but they affect the correctness of the claimed results.

major comments (2)
  1. [3.1] The statement "every edge might contain at most ⌈1/(2r)⌉ points from an r-independent set" is false. For r = 1/4, the three points at positions 0, 1/2, and 1 on a unit interval are pairwise at distance at least 1/2 = 2r, so a single edge can contain three points while ⌈1/(2r)⌉ = 2. The correct upper bound is ⌊1/(2r)⌋ + 1, and the approximation discussion that derives the performance guarantee 1 − 1/(k+1) needs to be reworked using this corrected bound rather than the false one.
  2. [3.3, Proposition 2] The proof for odd n is incomplete. The sentence "for odd numbers n we can straightforwardly take the colouring of an even bigger graph Γ(K_{n+1})" is not a valid reduction, because deleting the extra vertex and its incident edges from the constructed coloring does not induce a coloring of Γ(K_n). In the Figure 2 construction for Γ(K_4) with matching edges (1,2) and (3,4), delete vertex 4. On the surviving edge (1,3), the blue ball at distance 3/4 from 1 covers [1/4,1], the midpoint ball of (1,2) only touches vertex 1, and the red ball on (2,3) is too far to cover the open segment (0,1/4); hence that segment is uncovered. The even-n construction may be sound, but a separate odd-n construction or a correct reduction is needed to prove the upper bound.
minor comments (4)
  1. [3.1, Proposition 1] The proof of Proposition 1 says that every radius-1 ball centered at an interior point contains exactly one endpoint of the graph. This is not true: the midpoint of an edge contains both endpoints of that edge. The statement of the proposition is true, but the proof should be repaired, for instance by assigning to each interior point an arbitrary endpoint at distance < 1 and using the triangle inequality to show that the assignment is injective into V \ S_2.
  2. [3.3, Proposition 2] The phrase "any two balls of the same colour are distant from each other by 1/4" is ambiguous. If it means the distance between the closed balls, then it does establish disjointness, but the authors should state this explicitly; the center distance is at least 5/4, not 1/4.
  3. [3.4] Reference [5] and the in-text citation "Bodaender" should read "Bodlaender".
  4. [3.3] The term "continuous planar graph" is used in the (1/2, 3)-colourability conjecture but is not formally defined; a definition should be added so that the conjecture is unambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Proposition 2 is an explicit construction, and the cited prior work is used for background complexity results rather than as a load-bearing input to the paper's own claims.

full rationale

I walked the claimed derivation chain. The paper's principal new content is Proposition 2, which gives an upper bound on the 1/2-chromatic number of the continuous complete graph Γ(K_n). Its proof is a direct construction: it takes a maximal matching, assigns distinct colors to the matching edges, and places colored 1/2-radius balls at explicit distances 1/4 and 3/4 along the remaining edges. The proof does not invoke the conjecture, does not fit a parameter to the target quantity, and does not rely on any prior result to define the bound into existence. The surrounding sections cite prior work, including Grigoriev et al. [11], Hartmann et al. [16], and Faulkner [9], but these citations supply known complexity classifications, discretization results, and background definitions; they are not used as a substitute for proving Proposition 2. The skeptical concern about the odd-n case is a mathematical correctness issue: the sentence 'for odd numbers n we can straightforwardly take the colouring of an even bigger graph Γ(K_{n+1})' may not correctly restrict to Γ(K_n), since balls centered on deleted edges can be needed to cover surviving edges. That is a proof gap, not a circularity, because the conclusion χ_{1/2}(Γ(K_n)) ≤ ceil(n/2) is not assumed as an input and no derived quantity is equivalent by construction to data used to obtain it. Self-citations appear, but they are not load-bearing for the paper's central claims, and external benchmarks and published proofs make the cited results independent evidence. Hence no significant circularity is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are introduced; the paper reuses existing parameters such as the radius r. No new entities are postulated beyond the continuous graph concept already present in the metric graph literature. The proofs rely on standard graph theory and on the cited prior results.

assumptions (4)
  • domain assumption The shortest-path metric on a continuous graph is the sum of distances along rectifiable edges.
    Definition 3 defines distance via shortest path concatenation; the analysis of independent sets and covers relies on this metric.
  • standard math Seymour-Thomas theorem equating treewidth with bramble number plus one.
    Section 3.4 uses this to define continuous treewidth via the 1-bramble number.
  • standard math Four Color Theorem for planar graphs.
    Motivates the conjecture that continuous planar graphs are (1/2,3)-colorable.
  • standard math NP-hardness and inapproximability results for clique and chromatic number.
    Used in Sections 3.1 and 3.3 to pose approximation questions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems." pith.science (2026). https://pith.science/paper/RC2VHMW2

@misc{pith2026250114554,
  author       = {Pith},
  title        = {Pith review of: Combinatorial properties of continuous graphs: A survey of challenges, solutions and open problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RC2VHMW2}},
  note         = {Machine review of arXiv:2501.14554}
}
read the original abstract

Inspired by notorious combinatorial optimization problems on graphs, in this paper we consider a series of related problems defined using a metric space and topology determined by a graph. Particularly, we present the Independent Set, Vertex Cover, Chromatic Number and Treewidth problems on, so-called, continuous or metric graphs where every edge is represented by a unit-length continuous interval rather than by a pair of vertices. If any point of any unit-interval edge is considered as a possible member of a hitting set or a cover, the classical combinatorial problems become trickier and many open questions arise. Notably, in many real-life applications, such a continuous view of a graph is more natural than the classic combinatorial definition of a graph. The contribution of this paper is twofold: i) we survey the known results for optimization problems on continuous graphs, and ii) we create a list of open problems related to the continuous graphs.

Figures

Figures reproduced from arXiv: 2501.14554 by the authors.

Figure 1
Figure 1. Maximum independent set in combinatorial and in continuous graphs set of balls of radii r in Γ such that the centers of the balls are mutually distant from each other by at least 2r or, in other words, the intersection of any two balls from the set is a finite number of points in Γ. For a continuous graph Γ = (V, E), a trivial upper bound on αr(Γ) is n + m/r, where n = |V | and m is the number of (unit-length) edges… view at source ↗
Figure 2
Figure 2. ( 1 2 , 2)-colouring of Γ(K4) For this section, we came up with the following open questions. Colouring a complete continuous graph. Let Kn and Γ(Kn) be a complete (com￾binatorial) graph on n vertices and its continuous counterpart, respectively. A seemingly simple question to ask is: What is the 1 2 -chromatic number of Γ(Kn)? For example, in [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

  1. [1]

    Appel, W

    K. Appel, W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois Journal of Mathematics 21 (1977), 429–490

    work page 1977

  2. [2]

    Appel, W

    K. Appel, W. Haken, J. Koch, Every planar map is four colorable. Part II. Reducibil- ity, Illinois Journal of Mathematics 21 (1977), 491–567

    work page 1977

  3. [3]

    Bandelt, V

    H-J. Bandelt, V. Chepoi, Metric graph theory and geometry: A survey, Contemporary Mathematics 453 (2008), 49—86

    work page 2008

  4. [4]

    Birkhoff, D

    G.D. Birkhoff, D. C. Lewis, Chromatic polynomials, Transactions of the American Mathematical Society 60(3) (1946), 355–451

    work page 1946

  5. [5]

    Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing 25(6) (1996), 1305–1317

    H.L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing 25(6) (1996), 1305–1317

    work page 1996

  6. [6]

    Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret- ical Computer Science 209(1–2) (1998), 1—45

    H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret- ical Computer Science 209(1–2) (1998), 1—45

    work page 1998

  7. [7]

    Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are N P-complete, Discrete Mathematics 30(3) (1980), 289—293

    D.P. Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are N P-complete, Discrete Mathematics 30(3) (1980), 289—293

    work page 1980

  8. [8]

    Dinur, S

    I. Dinur, S. Safra, On the hardness of approximating minimum vertex cover, Annals of Mathematics 162(2005), 439–485

    work page 2005

Show all 24 references
  1. [9]

    Faulkner, A Relaxed Interpretation of Three Classic Vertex Problems, MSc Thesis, Maastricht University, The Netherlands (2018)

    K. Faulkner, A Relaxed Interpretation of Three Classic Vertex Problems, MSc Thesis, Maastricht University, The Netherlands (2018)

    2018

  2. [10]

    F. Frei, A. Ghazy, T.A. Hartmann, F. H¨ orsch, D. Marx, From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges, in: 35th International Symposium on Algorithms and Computation (ISAAC 2024), Leibniz International Proceedings in Informatics ...

    2024

  3. [11]

    Grigoriev, T.A

    A. Grigoriev, T.A. Hartmann, S. Lendl, G.J. Woeginger, Dispersing Obnoxious Fa- cilities on a Graph, Algorithmica 83 (2021), 1734–1749 12

    2021

  4. [12]

    Hartmann, Facility Location on Graphs, PhD The- sis, R WTH Aachen University, Germany (2022)

    T.A. Hartmann, Facility Location on Graphs, PhD The- sis, R WTH Aachen University, Germany (2022). Retrieved from https://publications.rwthaachen.de/record/951030

    2022

  5. [13]

    Hartmann, T

    T.A. Hartmann, T. Janßen, Approximating δ-Covering, in: M. Bie´ nkowski and M. Englert (eds.) Approximation and Online Algorithms (W AOA 2024), Lecture Notes in Computer Science, Volume 15269, Springer, Cham (2025)

    2025

  6. [14]

    Hartmann, S

    T.A. Hartmann, S. Lendl, Dispersing Obnoxious Facilities on Graphs by Round- ing Distances, in: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, 55:1–55:14, Schloss ...

    2022

  7. [15]

    Hartmann, D

    T.A. Hartmann, D. Marx, Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances, in: 42nd International Sympo- sium on Theoretical Aspects of Computer Science (STACS 2025), Leibniz Interna- tional Proceedings in Informatics (LIPIcs)...

    2025

  8. [16]

    Hartmann, S

    T.A. Hartmann, S. Lendl, G.J. Woeginger, Continuous facility location on graphs, Mathematical Programming 192 (2022), 207-–227

    2022

  9. [17]

    H ˚ astad, Clique is hard to approximate withinn1−ε, Acta Mathematica 182 (1999), 105–142

    J. H ˚ astad, Clique is hard to approximate withinn1−ε, Acta Mathematica 182 (1999), 105–142

    1999

  10. [18]

    Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, 1972

    R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, 1972

    1972

  11. [19]

    S. Khot, O. Regev, Vertex cover might be hard to approximate to within 2 − ε, Journal of Computer and System Sciences 74(3) (2008), 335–349

    2008

  12. [20]

    Megiddo, A

    N. Megiddo, A. Tamir, New results on the complexity of p-center problems, SIAM Journal on Computing , 12(4) (1983), 751-–758

    1983

  13. [21]

    Mugnolo, What is actually a metric graph? arXiv:1912.07549 (2021)

    D. Mugnolo, What is actually a metric graph? arXiv:1912.07549 (2021)

    2021 arXiv

  14. [22]

    Robertson, D.P

    N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, The Four-Colour Theorem, Journal of Combinatorial Theory Ser. B , 70(1) (1997), 2-–44

    1997

  15. [23]

    Seymour, R

    P.D. Seymour, R. Thomas, Graph searching and a minimax theorem for tree-width, Journal of Combinatorial Theory Ser. B 58 (1993), 239-–257

    1993

  16. [24]

    Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

    D. Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing 3 (2007), 103–128. 13

    2007

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.