{"id":"1594894e-ac5c-401c-999a-60a759ec8ddf","arxiv_id":"2501.13617","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every graph G, the r-dynamic chromatic number satisfies chi_r(G) <= (scol2(G)-1)r+1, so every bounded-expansion class has chi_r(G) in O(r).","lead":"The authors prove that any graph whose strong 2-coloring number is at most k can be r-dynamically colored with about (k-1)r+1 colors. This yields the first linear-in-r upper bound for every class of graphs of bounded expansion, including planar graphs and graphs of bounded genus.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5 relies on a false claim that the earlier neighborhood of v_{i+1} is a clique; the proof is repairable via mutual 2-accessibility, so the main result stands but needs revision.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing flaw in the central proof: the assertion that the earlier neighborhood is a clique is false, and without a substitute argument property 1 is unjustified. I confirmed the substitute argument: for two earlier neighbors a < b of v_{i+1}, the path a-v_{i+1}-b has inner vertex v_{i+1} > b, putting a in SReach2(b); strong properness then makes their colors differ. This is a one-line repair that uses precisely the strong 2-coloring definition, so the main bound (k-1)r+1 is correct. No counterexample to Theorem 5 or Corollary 6 emerged. The paper also contains a smaller, independent error in the row-treewidth constant: Lemma 13 with t=2 yields scol2(G) <= 5(rtw(G)+1), so Theorem 5 gives chi_r <= (5*rtw(G)+4)r+1, not the claimed 5*rtw(G)*r+1. Both issues require a revision of the write-up but do not invalidate the core contribution. Therefore the verdict remains CONDITIONAL, as the reader concluded; no further adjustment is needed.","tokens_in":10898,"tokens_out":14209,"duration_ms":125333,"concrete_test":"Run the greedy construction on C4 with the order (v1,v2,v3,v4) and any r. The printed claim 'N_{G4}(v4) is a clique' fails because v1 and v3 are non-adjacent. Then verify the repair: v1 is in SReach2(v3) via the path v1-v4-v3, so every strongly proper coloring gives v1 and v3 distinct colors; hence property 1 holds. If this verification succeeds, Theorem 5's bound remains valid with a corrected proof. Additionally, recompute Corollary 14 from Lemma 13 with t=2 to confirm the bound is (5*rtw(G)+4)r+1 rather than 5*rtw(G)*r+1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the greedy proof of Theorem 5, property 1 is justified by: 'property 1 is always satisfied, since the neighborhood of v_{i+1} in G_{i+1} is a clique and hence all vertices in N_{G_{i+1}}(v_{i+1}) have distinct colors as phi_i is proper.' This is false for an arbitrary order witnessing scol2(G) <= k. Example: C4 with the order v1,v2,v3,v4 has scol2 <= 3, but the earlier neighbors of v4 are v1 and v3, which are not adjacent, so N_{G4}(v4) is not a clique. The proof as written therefore does not establish property 1, which is essential for the greedy extension. The gap is repairable: if a and b are two earlier neighbors of v_{i+1} and a < b, then the path a-v_{i+1}-b has length 2 and its only inner vertex v_{i+1} satisfies v_{i+1} > b, so a is in SReach2(b); because phi_i is strongly proper, phi(a) != phi(b). Thus all earlier neighbors get distinct colors and property 1 holds. The n2/n3 counting then goes through unchanged, so Theorem 5's bound (k-1)r+1 survives. Separately, Corollary 14/Theorem 3.3 state chi_r <= 5*rtw(G)*r+1, but Lemma 13 with t=2 gives scol2(G) <= 5(rtw(G)+1), which yields chi_r <= (5*rtw(G)+4)r+1, not the stated bound; this is an independent constant error.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every graph G and integer r, the r-dynamic chromatic number satisfies chi_r(G) <= (scol2(G)-1)r+1, where scol2 is the strong 2-coloring number. It then derives that every graph class of bounded expansion has r-dynamic chromatic numbers bounded by a linear function of r, and it provides explicit bounds in terms of treewidth and row-treewidth. The proofs are short and rely on a greedy extension argument together with known bounds on strong coloring numbers. The paper also discusses limitations of generalizing the result to nowhere dense classes and gives an example of a somewhere dense class with bounded r-dynamic chromatic number.","tokens_in":11244,"tokens_out":2237,"duration_ms":20599,"significance":"If correct, the main result is a clean and useful generalization: it subsumes several earlier bounds for planar graphs, bounded-genus graphs, and minor-closed classes under the single framework of strong coloring numbers, and it gives the first linear-in-r bound for all bounded-expansion classes. The paper is a concise note that connects r-dynamic coloring to well-studied sparsity parameters, and the proof of Theorem 5 is conceptually attractive. The explicit bound for treewidth is also of independent interest. However, two specific issues in the current manuscript—an incorrect justification in the proof of Theorem 5 and a constant error in the row-treewidth corollary—need to be repaired before the paper can be accepted.","major_comments":[{"comment":"The justification of property 1 is false. The paper states that the neighborhood of v_{i+1} in G_{i+1} is a clique, but for an arbitrary linear order witnessing scol2(G) <= k this need not hold; e.g., for C4 with order v1,v2,v3,v4, the earlier neighbors of v4 are v1 and v3, which are not adjacent, and this order satisfies scol2 <= 3. The conclusion is nevertheless salvageable: if a and b are two earlier neighbors of v_{i+1} with a < b, then the path a-v_{i+1}-b has length 2 and its inner vertex v_{i+1} is greater than b, so a belongs to SReach2(b); since phi_i is strongly proper, phi_i(a) != phi_i(b). Thus all earlier neighbors of v_{i+1} receive distinct colors and property 1 holds. Please replace the clique argument with this mutual 2-accessibility argument.","section":"Section 3, proof of Theorem 5"},{"comment":"There is a constant error in the row-treewidth bound. Lemma 13 with t=2 gives scol2(G) <= 5(rtw(G)+1), not 5 rtw(G). Substituting into Theorem 5 yields chi_r(G) <= (5 rtw(G)+4)r+1, not the claimed 5 rtw(G) r+1. The same issue affects Theorem 3(3) in the introduction. The bound remains linear in r, but all three statements (Theorem 3(3), Lemma 13 as applied, and Corollary 14) need to be corrected consistently.","section":"Section 4, Lemma 13 and Corollary 14"}],"minor_comments":[{"comment":"In the proof of Lemma 7, the sentence 'This already proves that scol1(G) <= k+1' uses a reverse perfect elimination ordering; it may be helpful to explicitly note that a perfect elimination ordering is one where right neighborhoods form cliques, so reversing it makes left neighborhoods cliques.","section":"Section 4, Lemma 7"},{"comment":"The paragraph discussing the subdivision example says 'scol1(K'_n) <= 3', but the argument uses that all original vertices appear before subdivision vertices; this is clear but a short explanation of why scol1 is at most 3 would improve readability.","section":"Section 3, after Theorem 5"},{"comment":"In Lemma 15, the assertion that SReach2(u) = {u} for every original vertex u relies on the fact that each edge is subdivided at least twice, so original vertices are at distance at least 3 from each other; this is correct but could be stated explicitly.","section":"Section 5, Lemma 15"}],"recommendation":"major_revision","confidential_remarks":"The paper is a short and readable note whose main idea is sound. The proof gap in Theorem 5 is localized and has a straightforward fix, and the row-treewidth constant error is a minor arithmetic issue; neither undermines the central result. I recommend major revision because two load-bearing statements in the current version are not correct as written, even though both are easily repairable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nThe main result is real: Theorem 5 gives chi_r(G) ≤ (scol2(G)-1)r+1, and the bounded-expansion corollary follows immediately. That unifies the existing planar and genus bounds under one parameter, which is the kind of thing people in the area will want. The technique is also nice — the greedy extension with strongly proper colorings is clean and should be reusable.\n\nThe proof of Theorem 5 has a false justification, though. Property 1 is said to follow because the earlier neighborhood of v_{i+1} is a clique. That's not true for arbitrary optimal scol2 orders — C4 with order v1,v2,v3,v4 gives scol2 ≤ 3 but earlier neighbors of v4 (v1 and v3) are nonadjacent. The property actually holds because any two earlier neighbors are mutually 2-accessible via v_{i+1}, so a strongly proper coloring makes them distinct. That's an easy repair, and the counting n2+n3 < d goes through unchanged.\n\nThere is a second, independent error: Corollary 14 states chi_r ≤ 5·rtw(G)·r+1, but Lemma 13 with t=2 gives scol2(G) ≤ 5(rtw(G)+1), which yields chi_r ≤ (5rtw(G)+4)r+1. The stated bound even fails for paths, where rtw=0. This is a constant mistake, not a conceptual one.\n\nI also had a small worry about the proof of Lemma 13: the projection argument from the product to H doesn't obviously preserve the \"inner vertices to the right\" condition, because a vertex in a later layer is greater in the product order regardless of its H-index. The lemma is likely true via the analogous layered-treewidth bound, but the written proof needs tightening.\n\nOverall, the central theorem is correct and the paper is worth engaging with. A serious referee should send it back for minor revision. I'd cite it.","headline":"Clean main bound, two repairable proof slips.","tokens_in":11777,"tokens_out":6181,"would_cite":true,"duration_ms":54568,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C10","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the r-dynamic chromatic number of any graph is controlled by its strong 2-coloring number, giving the linear bound (k−1)r+1 whenever scol2(G) ≤ k.","keywords":["r-dynamic coloring","strong 2-coloring number","bounded expansion","treewidth","row-treewidth","r-hued coloring","graph coloring"],"falsifier":"Enumerate all graphs on up to eight vertices, compute $\\mathrm{scol}_2(G)$ exactly over all vertex orders, and compare $\\chi_r(G)$ with $(k-1)r+1$ for small $r$; a single violation would refute Theorem 5, while a 4-cycle check isolates whether the proof's clique claim must be replaced by the mutual $2$-accessibility argument.","tokens_in":10716,"feed_emoji":"🎨","tokens_out":11074,"duration_ms":81294,"temperature":0.7,"pith_summary":"The paper proves that the r-dynamic chromatic number of a graph is controlled by its strong 2-coloring number: if no ordering of the vertices forces any vertex to have more than k earlier vertices within distance two (with later internal vertices allowed), then (k−1)r+1 colors suffice for an r-dynamic coloring. Because many sparse graph classes—planar graphs, bounded-treewidth graphs, and every graph class of bounded expansion—have bounded strong 2-coloring numbers, the result implies their r-dynamic chromatic numbers grow at most linearly with r even when maximum degree is unbounded. The paper also turns the general bound into explicit constants for treewidth and row-treewidth, and notes that subdividing every edge of a graph at least twice yields 2r+1 colors regardless of the original graph.","feed_headline":"One graph parameter bounds r-dynamic colorings","feed_subtitle":"A single structural number yields linear-in-r color bounds for planar and minor-closed graph classes.","key_machinery":"The engine is the strong 2-coloring number $\\mathrm{scol}_2(G)$, the minimum over all linear vertex orders of the largest set of vertices that can reach a fixed vertex by a path of length at most two whose internal vertices come later in the order. The argument rides on a greedy coloring that maintains two invariants: strong propriety (a vertex never shares a color with an earlier vertex from which it is reachable by such a path) and weak $r$-dynamicity at every vertex. The counting step bounds the two kinds of forbidden colors separately, and Zhu's theorem identifying bounded expansion exactly with bounded strong coloring numbers (Theorem 4) converts the parameter bound into a statement about whole graph classes.","core_discovery":"The central claim is Theorem 5: for all $r,k\\in\\mathbb{N}$, if $\\mathrm{scol}_2(G)\\le k$ then $\\chi_r(G)\\le (k-1)r+1$. The proof colors vertices one at a time in an order witnessing the strong 2-coloring number, maintaining a 'strongly proper' coloring—no two vertices within distance two that are ordered consistently receive the same color—and a per-vertex condition that each neighborhood already uses $\\min(r,\\deg(v))$ colors. At each step it counts at most $k-1$ forbidden colors from distance-two constraints and at most $(k-1)(r-1)$ from the dynamic-color constraint, so the total stays below $(k-1)r+1$. Corollary 6 then states that for any graph class of bounded expansion, the $r$-dynamic chromatic numbers of its graphs are bounded by a linear function of $r$.","pith_inferences":["The additive-versus-multiplicative question the paper raises for treewidth suggests the $(k-1)r+1$ bound is probably not tight; a natural next step is to decide whether $\\chi_r(G)$ can be kept in $O(\\mathrm{tw}(G)+r)$ for all graphs.","Because the stated clique justification for one proof step can fail on a 4-cycle, the theorem's correctness depends on replacing that step with a mutual $2$-accessibility argument; a reader checking the proof should confirm that replacement before relying on the bound.","The same greedy two-invariant scheme may transfer to other parameters that are bounded on sparse classes, such as the weak coloring number or generalized coloring numbers, yielding similar linear bounds for other distance-type colorings.","The discussion of subdividing every edge at least twice shows the hypothesis 'bounded expansion' is sufficient but not necessary: some classes with unbounded expansion still have linear $r$-dynamic chromatic number, so the true boundary of the phenomenon lies elsewhere."],"forward_implications":["For every graph class of bounded expansion, there is a constant $c$ such that $\\chi_r(G)\\le c\\cdot r$ for all graphs in the class and all $r$, with no dependence on maximum degree.","Graphs of treewidth $k$ satisfy $\\chi_r(G)\\le k\\cdot r+1$.","Graphs of row-treewidth $k$ satisfy $\\chi_r(G)\\le 5k\\cdot r+1$.","For $(g,k)$-planar graphs, $\\chi_r(G)\\le 5(4g+6)(k+1)r+1$, giving a linear-in-$r$ and linear-in-genus bound that generalizes earlier planar and genus results.","Every graph obtained by subdividing each edge at least twice satisfies $\\mathrm{scol}_2(S)\\le 3$ and hence $\\chi_r(S)\\le 2r+1$, even though the class of such subdivisions need not have bounded expansion."],"supporting_citations":[{"why":"Introduces strong k-coloring numbers and shows they bound the acyclic chromatic number, supplying the parameter at the heart of the proof.","marker":"[17]"},{"why":"Zhu's theorem characterizes bounded expansion by bounded strong coloring numbers, turning the scol2 bound into the corollary for bounded-expansion classes.","marker":"[37]"},{"why":"Lai et al. introduce r-dynamic (conditional) colorings and give the complete-subdivision example showing that sparsity alone does not bound chi_r.","marker":"[21]"},{"why":"Song and Lai's planar bound 2r+16 is the prior result that the new linear bound generalizes.","marker":"[33]"},{"why":"Loeb et al. give genus-dependent linear bounds, which the new bound also covers and extends.","marker":"[23]"},{"why":"Van den Heuvel and Wood's bound on scolt for (g,k)-planar graphs is plugged into the main theorem to produce Corollary 11.","marker":"[34]"},{"why":"Dujmovic et al. provide the row-treewidth machinery and the planar row-treewidth bound that underlies Corollary 14.","marker":"[7]"},{"why":"Grohe et al. give scoln(G)=tw(G)+1, the identity used to derive the treewidth bound in Lemma 7.","marker":"[11]"},{"why":"Nesetril and Ossona de Mendez define bounded expansion, the graph-class framework in which Corollary 6 is stated.","marker":"[27]"}],"fun_headline_variants":["Strong 2-coloring number bounds r-dynamic chromatic number","Linear bound on r-dynamic colorings from strong 2-coloring","Bounded expansion yields linear r-dynamic color bound","r-Dynamic chromatic number bounded via strong 2-coloring number"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's greedy step leans on the claim that the earlier neighbors of the newly added vertex form a clique, so that a proper coloring already distinguishes them; this can fail for an optimal order (a 4-cycle is a counterexample), and the replacement argument via mutual $2$-accessibility is not given in the paper.","fun_headline_variants_meta":{"raw":{"variants":["Strong 2-coloring number bounds r-dynamic chromatic number","Linear bound on r-dynamic colorings from strong 2-coloring","Bounded expansion yields linear r-dynamic color bound","r-Dynamic chromatic number bounded via strong 2-coloring number"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00061,"raw_usage":{"total_tokens":2790,"prompt_tokens":849,"completion_tokens":1941,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":465,"completion_tokens_details":{"reasoning_tokens":1869}},"tokens_in":465,"tokens_out":1941,"duration_ms":12749,"temperature":1.0,"reasoning_tokens":1869,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:49:13.331065+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all graphs on up to eight vertices, compute $\\mathrm{scol}_2(G)$ exactly over all vertex orders, and compare $\\chi_r(G)$ with $(k-1)r+1$ for small $r$; a single violation would refute Theorem 5, while a 4-cycle check isolates whether the proof's clique claim must be replaced by the mutual $2$-accessibility argument.","supporting_citations":[{"cited_title":"Orderings on graphs and game coloring number","cited_arxiv_id":null,"evidence_quote":"Introduces strong k-coloring numbers and shows they bound the acyclic chromatic number, supplying the parameter at the heart of the proof."},{"cited_title":"Conditional colorings of graphs","cited_arxiv_id":null,"evidence_quote":"Lai et al. introduce r-dynamic (conditional) colorings and give the complete-subdivision example showing that sparsity alone does not bound chi_r."},{"cited_title":"Upper bounds of r-hued colorings of planar graphs","cited_arxiv_id":null,"evidence_quote":"Song and Lai's planar bound 2r+16 is the prior result that the new linear bound generalizes."},{"cited_title":"Dynamic coloring parameters for graphs with given genus","cited_arxiv_id":null,"evidence_quote":"Loeb et al. give genus-dependent linear bounds, which the new bound also covers and extends."},{"cited_title":"Coloring and covering nowhere dense graphs","cited_arxiv_id":null,"evidence_quote":"Grohe et al. give scoln(G)=tw(G)+1, the identity used to derive the treewidth bound in Lemma 7."}],"review_version":1}