{"id":"3ebaf222-06ab-41f8-a8db-81da9cf939ce","arxiv_id":"2501.14554","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of complexity results and open problems for independent set, vertex cover, coloring, and treewidth on continuous graphs, with a new upper bound for the coloring number of complete continuous graphs.","lead":"This survey examines how classic graph problems change when every edge is a continuous unit interval instead of a simple connection between two points, and it collects open problems about these 'continuous graphs'. It is a useful map of recent work, but some of the new claims and proofs need correction before the survey can be fully trusted.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2's proof is incomplete for odd n: the claimed reduction to Γ(K_{n+1}) by deleting a vertex destroys coverage of the surviving edges, so the upper bound is not established for odd n.","rationale":"The reader's weakest assumption concerns the disjointness of same-colored balls in Proposition 2. That concern is not fatal: in the even-n construction, the same-color center distances are all strictly greater than 1 (minimum gap between balls is 1/4), so the coloring is proper once the phrase 'distant by 1/4' is read as the gap between the balls. The more serious problem is the odd-n reduction, which the reader did not identify. The manuscript's assertion that a coloring of Γ(K_{n+1}) straightforwardly yields one of Γ(K_n) is false for the constructed coloring: deleting the extra vertex removes balls that are needed to cover the surviving edges. The n=3 example above demonstrates the failure explicitly. This does not refute the bound, since a direct 2-coloring of Γ(K3) plausibly exists, but it means the proof as written covers only even n. I also confirm the reader's note that the per-edge bound in Section 3.1, 'every edge might contain at most ceil(1/(2r)) points', is false for r=1/4 because the endpoints 0, 1/2, 1 are three valid points on one edge; however, that error is in the survey discussion rather than in the main Proposition 2. Since the central claim is likely true but the proof has a genuine gap for odd n, the appropriate disposition remains CONDITIONAL, matching the reader's verdict.","tokens_in":10012,"tokens_out":26965,"duration_ms":235243,"concrete_test":"Implement the Proposition 2 construction for n=4 with matching edges (1,2) and (3,4), delete vertex 4 and all incident edges, and test whether every point of the remaining Γ(K3) is covered by the remaining 1/2-balls. The open segment (0,1/4) on edge (1,3) is uncovered, so the claimed reduction fails; then, to check whether the bound itself survives, search for a direct (1/2,2)-coloring of Γ(K3) using four balls on the 3-cycle.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The even-n part of Proposition 2 is essentially correct: for each matching edge i, all color-i centers are the midpoint of edge i and points at distance 3/4 from its two endpoints on edges to other matching edges; direct distance checks give same-color center distances at least 5/4, so the balls are disjoint, and the remaining 1/4-neighborhoods at endpoints are covered by centers at distance 1/4 from those endpoints on other incident edges. The proof fails for odd n, however. The paper states that for odd n one can 'straightforwardly take the colouring of an even bigger graph Γ(K_{n+1})', but a coloring of Γ(K_{n+1}) does not restrict to Γ(K_n) by deleting the extra vertex and its incident edges: the balls centered on the deleted edges are exactly what cover the last quarter of surviving edges near that vertex. Concretely, in the Figure 2 construction for Γ(K4) with matching edges (1,2) and (3,4), delete vertex 4 and all incident edges. On surviving edge (1,3), the blue ball at 3/4 from 1 covers [1/4,1], the midpoint ball of (1,2) covers only vertex 1, and the red ball on (2,3) at 1/4 from 2 is at distance greater than 1/2 from every point of (1,3). Hence the open segment (0,1/4) on (1,3) is uncovered. The odd-n upper bound may still be true, but the proof given does not establish it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10353,"tokens_out":20717,"duration_ms":185384,"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":[{"comment":"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.","section":"3.1"},{"comment":"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.","section":"3.3, Proposition 2"}],"minor_comments":[{"comment":"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.","section":"3.1, Proposition 1"},{"comment":"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.","section":"3.3, Proposition 2"},{"comment":"Reference [5] and the in-text citation \"Bodaender\" should read \"Bodlaender\".","section":"3.4"},{"comment":"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.","section":"3.3"}],"recommendation":"major_revision","confidential_remarks":"The survey portion of the paper appears to be a fair and useful account of the recent literature on continuous graphs, and the citations to the authors' own work and to Hartmann's thesis are normal for this specialized area. The main risk is the new material: the capacity bound in Section 3.1 and the odd-n reduction in Proposition 2 are both incorrect as written. Both seem fixable without changing the scope of the paper, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the survey is worth having, but the new mathematics is not reliable. The authors map the known results for continuous (metric) graph versions of independent set, vertex cover, chromatic number, and treewidth, and they collect a sensible list of open problems. That survey content is the paper's real value.\n\nThe new result, Proposition 2, claims χ_{1/2}(Γ(K_n)) ≤ ⌈n/2⌉. The even-n construction is basically sound: the same-color ball centers are far enough apart, with the balls separated by about a quarter of an edge, and coverage checks out. But the odd-n case is not handled. A coloring of Γ(K_{n+1}) does not restrict to Γ(K_n) by deleting a vertex. Balls centered on edges incident to the deleted vertex disappear, and those are exactly the balls that cover the first quarter of some surviving edges near that vertex. In the Figure 2 construction, remove vertex 4; edge (1,3) then has its (0,1/4) segment uncovered. The odd-n upper bound may still be true, but this proof does not show it.\n\nThere is also a false statement in Section 3.1: for r ≤ 1/2, an edge can contain at most ⌈1/(2r)⌉ points of an r-independent set. For r=1/4, three points (at 0, 1/2, 1) fit on a unit edge. The correct upper bound is floor(1/(2r))+1. This error does not collapse the section, but it should be fixed.\n\nMinor: the proof of Proposition 1 says every 1-radius ball in the packing contains exactly one endpoint, which is false (a ball centered in the middle of an edge contains both endpoints). The proposition may be true, but the proof needs repair.\n\nThe survey is a decent entry point for someone new to continuous graphs or looking for open problems. It is not a deep-results paper. The citation pattern is normal for a survey by people inside the area, with heavy reliance on Hartmann and colleagues for good reason. I would send this to review only with the clear expectation that the odd-n proof, the capacity bound, and the Proposition 1 proof be corrected. As is, I would not want it published in its current form.","headline":"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.","tokens_in":10833,"tokens_out":9960,"would_cite":false,"duration_ms":76456,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C69","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["continuous graphs","metric graphs","r-independent set","r-cover","chromatic number","treewidth","open problems","complete graph"],"falsifier":"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.","tokens_in":9825,"feed_emoji":"🎨","tokens_out":11211,"duration_ms":88151,"temperature":0.7,"pith_summary":"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.","feed_headline":"Coloring complete continuous graphs needs at most ⌈n/2⌉ colors","feed_subtitle":"Physical networks treat edges as intervals, and this construction halves the color count of K_n.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the polynomial-time and NP-hardness results for maximum $r$-independent sets on continuous graphs, for small and large rational radii.","marker":"[11]"},{"why":"proves rational-distance discretization and polynomial-size certificates, and NP-hardness for all real non-unit-fraction radii for both the cover and independent set problems.","marker":"[14]"},{"why":"establishes the complexity of the minimum $r$-cover problem: polynomial for unit fractions, NP-hard otherwise, and polynomial for $r=1$ via matching.","marker":"[16]"},{"why":"proves the $\\alpha_1 + \\beta_1 = n$ duality for $r=1$ and the discretization results for $r$-independent sets.","marker":"[12]"},{"why":"introduces brambles and proves bramble number plus one equals treewidth, the basis for the paper's continuous treewidth definition.","marker":"[23]"},{"why":"provides the inapproximability of chromatic number and max clique that motivates the continuous approximation questions.","marker":"[24]"},{"why":"shows clique is hard to approximate within $n^{1-\\varepsilon}$, supporting the stated hardness for independent set inapproximability.","marker":"[17]"}],"fun_headline_variants":["Continuous K_n colorable with ⌈n/2⌉ colors, no more","Half-color bound for continuous complete graphs","Edge intervals cut K_n coloring to ⌈n/2⌉ colors","Survey yields new ⌈n/2⌉ coloring bound for continuous graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Continuous K_n colorable with ⌈n/2⌉ colors, no more","Half-color bound for continuous complete graphs","Edge intervals cut K_n coloring to ⌈n/2⌉ colors","Survey yields new ⌈n/2⌉ coloring bound for continuous graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000412,"raw_usage":{"total_tokens":2102,"prompt_tokens":886,"completion_tokens":1216,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":1139}},"tokens_in":502,"tokens_out":1216,"duration_ms":10892,"temperature":1.0,"reasoning_tokens":1139,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:02:30.168643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Grigoriev, T.A","cited_arxiv_id":null,"evidence_quote":"supplies the polynomial-time and NP-hardness results for maximum $r$-independent sets on continuous graphs, for small and large rational radii."},{"cited_title":"Hartmann, S","cited_arxiv_id":null,"evidence_quote":"proves rational-distance discretization and polynomial-size certificates, and NP-hardness for all real non-unit-fraction radii for both the cover and independent set problems."},{"cited_title":"Hartmann, S","cited_arxiv_id":null,"evidence_quote":"establishes the complexity of the minimum $r$-cover problem: polynomial for unit fractions, NP-hard otherwise, and polynomial for $r=1$ via matching."},{"cited_title":"Hartmann, Facility Location on Graphs, PhD The- sis, R WTH Aachen University, Germany (2022)","cited_arxiv_id":null,"evidence_quote":"proves the $\\alpha_1 + \\beta_1 = n$ duality for $r=1$ and the discretization results for $r$-independent sets."},{"cited_title":"Seymour, R","cited_arxiv_id":null,"evidence_quote":"introduces brambles and proves bramble number plus one equals treewidth, the basis for the paper's continuous treewidth definition."},{"cited_title":"Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number","cited_arxiv_id":null,"evidence_quote":"provides the inapproximability of chromatic number and max clique that motivates the continuous approximation questions."},{"cited_title":"H ˚ astad, Clique is hard to approximate withinn1−ε, Acta Mathematica 182 (1999), 105–142","cited_arxiv_id":null,"evidence_quote":"shows clique is hard to approximate within $n^{1-\\varepsilon}$, supporting the stated hardness for independent set inapproximability."}],"review_version":1}