{"id":"d2164368-70f1-427c-8957-b82e8b14cb09","arxiv_id":"1908.05066","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Every d-degenerate graph with maximum degree Δ ≥ 9.818d admits an equitable tree-k-coloring for every integer k ≥ (Δ+1)/2, confirming the Equitable Vertex Arboricity Conjecture for low-degeneracy graphs.","lead":"This paper proves that every graph whose local sparsity, or degeneracy, is about ten times smaller than its maximum degree can be partitioned into nearly equal forests using at most (Δ+1)/2 colors. The result is a partial confirmation of the long-standing Equitable Vertex Arboricity Conjecture and improves the previous exponential bound to a linear one.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof is internally coherent, with the cited Lemma 2.2 as the main external dependency to verify.","rationale":"The reader's conditional verdict rests on the unproved cited Lemma 2.2 and on unverified numerical estimates. I checked the numerical estimates with exact arithmetic: f(0.286) ≈ 8.397 < 8.789, θ has its maximum at the endpoints on [4.1818, 6] with θ(4.1818) < 9.81792 and θ(6) ≈ 9.515 < 9.818, and the φ(0.5681d) computations are negative with a positive margin under k > 4.909d. The structural induction is coherent: the recoloring in Case 2 respects both the forest condition and the size constraints, and the derivation from (2.23) through (2.28) is algebraically sound. The one truly load-bearing assumption is Lemma 2.2, which is cited rather than proved; this is standard mathematical practice, and I found no internal reason to doubt it. The 'r ≥ 3' remark is not load-bearing because r > 0 suffices for the displayed chain. Consequently, the reader's conditional verdict remains appropriate, and no verdict change is needed.","tokens_in":9644,"tokens_out":55655,"duration_ms":549400,"concrete_test":"Consult the original Kostochka–Nakprasit paper [11] and verify the exact statement of Lemma 2.2: ordering by nonincreasing degree and the strict bound deg_G(v_i) < d(1 + n/i). If the original lemma uses a different ordering or has an extra hypothesis, re-derive the proof's uses at (2.7), (2.13), and (2.20). If the lemma matches, the central proof stands without further modification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. Re-reading the proof, the induction, the recoloring argument, and the numerical inequalities all check out: Case 1 forces Δ/d < 8.789, Case 2 forces y < 0.5681d via convexity arguments, and the final subcase gives Δ/d < θ(λ) < 9.818 on the admissible interval λ ∈ [4.1818, 6]. The only genuinely load-bearing external input is Lemma 2.2 from Kostochka and Nakprasit [11], cited without proof; it is used to obtain μ < n/(λ−1), in the bound at (2.13), and in (2.20). If that lemma were misstated or inapplicable, those bounds would collapse. Since the lemma is a published result and the stated degree-ordering version is plausible, this is not a demonstrated flaw, but it is the one assumption worth checking. A minor wording issue appears in the second branch of the y < 0.5681d claim, where the text cites 'the fact that r ≥ 3'; r ≥ 3 is not generally forced, but the subsequent chain only needs r > 0, which follows in that branch, so the argument remains repairable.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 1.5: every d-degenerate graph with maximum degree at most Δ is equitably tree-k-colorable for every integer k ≥ (Δ+1)/2, provided that Δ ≥ 9.818d. This confirms the Equitable Vertex Arboricity Conjecture in the low-degeneracy regime and replaces the previous exponential sufficient condition Δ ≥ 2·3^{d-1}−1 with a linear one. The proof is by induction on the number of vertices. It colors a high-degree initial segment using the induction hypothesis, then extends the coloring to the remaining vertices by an online recoloring procedure that preserves forest color classes and balanced sizes. The extension step is analyzed in two cases according to the position of the first uncolorable vertex; both cases lead to numerical contradictions (i ≤ n/2 forces Δ/d < 8.789, and i > n/2 forces Δ/d < θ(λ) < 9.818 on the admissible λ-interval).","tokens_in":9829,"tokens_out":35822,"duration_ms":326798,"significance":"If correct, the result is a genuine advance: it gives the first linear-in-d sufficient condition for the Equitable Vertex Arboricity Conjecture for d-degenerate graphs, where the only previously known general condition was exponential. The proof is detailed and verifiable, and the numerical threshold 9.818 is explicit. The main external dependency is Lemma 2.2 of Kostochka and Nakprasit, cited without proof; I checked that lemma and found it valid: in a degeneracy ordering each vertex has at most d later neighbors, so orienting edges to the later endpoint gives total indegree equal to the number of edges, which is < dn, yielding deg(v_i) < d(1+n/i). The local inaccuracies I found are confined to the Case 2 estimates and are repairable without changing the proof strategy. I therefore regard the central claim as sound.","major_comments":[],"minor_comments":[{"comment":"The strict inequality in (2.22) is not correct in the boundary case A' = ∅ and |A| = r: then (λ−1)d|A'| = 2y(|A|−r) = 0, so the displayed chain has equality where the text writes a strict inequality. The desired conclusion (2.23) still follows in that case, because |A| = r together with (2.21) gives |B| = t(k−y)−r, and the same upper bound e(G*) < d(kt−r)+r(r−1)/2 yields (2.23) with strictness. Please rewrite this passage so that the boundary case is handled explicitly.","section":"§2, equations (2.22)–(2.23)"},{"comment":"The sentence 'Using (2.1), (2.23) and the fact that r ≥ 3' is inaccurate: r ≥ 3 is not a consequence of the assumptions (for instance, d = 2 forces r = 0 by (2.1)). The displayed manipulation only needs t ≥ 3 in the second inequality; moreover, in the branch φ(y) < 0, the case r = 0 is already impossible because it would contradict (2.23). Please replace the reference to r ≥ 3 by the correct justification.","section":"§2, paragraph after (2.23)"},{"comment":"The conclusion 'λ < 4.1818 or λ > 6' from the endpoint values θ(4.1818) < 9.81792 and θ(6) < 9.515 relies on the fact that θ has its maximum on the interval [4.1818, 6] at an endpoint. This is true because θ'(λ) = (λ² − 6λ + 4.8638)/(λ−3)² has a single interior critical point, but the manuscript does not state this; it should be made explicit.","section":"§2, Subcase 2.2"},{"comment":"The received text contains numerous OCR artifacts, including corrupted square-root symbols in the derivative computation in Case 1, missing parentheses in the display around (2.6), and split words such as 'graph s'. These make some formulas hard to read. Please ensure that the final submission is a cleanly typeset version.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"I believe the paper is publishable after a minor revision. The two technical points in Case 2 are local and repairable, and they do not affect the main theorem. The result is a solid contribution to the equitable arboricity literature and fits the journal's scope. The received PDF is badly OCR-corrupted, so the authors should be asked to supply a clean version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe big news is that Theorem 1.5 replaces the old exponential condition Δ ≥ 2·3^{d−1}−1 with Δ ≥ 9.818d for d-degenerate graphs. That is a genuine improvement and a real step toward EVAC, not a repackaging. The proof runs an induction with a recoloring algorithm, and the new twist is fixing a rainbow coloring of the added clique Kr so that the tree-coloring reduction from G∪Kr to G works. The case analysis is detailed; I spot-checked the numerical bounds (Case 1 gives Δ/d < 8.789, Case 2's θ(λ) peaks below 9.818 on the relevant interval) and they are consistent.\n\nThe paper does what it claims, and the writing is honest about where the limits are. It doesn't solve EVAC, and the open problems at the end are sensible.\n\nSoft spots, in order of importance. First, the proof leans on Lemma 2.2 from Kostochka and Nakprasit, which is quoted without proof. The whole induction and the bounds in (2.13) and (2.20) depend on it. It is a published result and the stated form is plausible, so this is a \"verify before building on it\" caveat, not a discovered flaw. Second, the constant 9.818 is given as a decimal; the authors should specify the exact rational (or interval) behind it so the margins can be checked. Third, the arXiv text has OCR artifacts that obscure a few symbols; a clean version is essential for refereeing. Minor: in Case 2, the text cites \"the fact that r ≥ 3\" where r ≥ 3 is not generally forced, but the chain only needs r > 0, which holds, so the argument is repairable.\n\nWho should read this: anyone working on equitable colorings, vertex arboricity, or degenerate graphs. It is a solid incremental result with a checkable proof. I would send it to a serious referee; it deserves the time.\n\nBest,","headline":"Solid proof of a linear degeneracy threshold for equitable vertex arboricity; the main caveat is an unproved external lemma and a decimal constant.","tokens_in":10420,"tokens_out":2648,"would_cite":true,"duration_ms":22884,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every d-degenerate graph with maximum degree at most Δ is equitably tree-k-colorable for every integer k ≥ (Δ+1)/2 whenever Δ ≥ 9.818d, confirming the Equitable Vertex Arboricity Conjecture for graphs whose…","keywords":["equitable tree-coloring","vertex arboricity","equitable coloring","d-degenerate graph","degeneracy","maximum degree","Equitable Vertex Arboricity Conjecture"],"falsifier":"Search for a $d$-degenerate graph with maximum degree $\\Delta \\ge 9.818d$ that is not equitably tree-$k$-colorable for $k = \\lceil(\\Delta+1)/2\\rceil$; the paper predicts no such graph exists, so any counterexample found would disprove Theorem 1.5. A direct check of the load-bearing ordering lemma—comparing $\\deg_G(v_i)$ with $d(1+n/i)$ in every $d$-degenerate graph—is a more localized experiment that would test the proof's foundation even if the theorem itself still held.","tokens_in":9387,"feed_emoji":"🌲","tokens_out":17053,"duration_ms":142798,"temperature":0.7,"pith_summary":"This paper establishes the Equitable Vertex Arboricity Conjecture for all graphs whose degeneracy is small compared with their maximum degree. It proves that every $d$-degenerate graph with maximum degree at most $\\Delta$ admits an equitable tree-$k$-coloring for every integer $k \\ge (\\Delta+1)/2$, provided $\\Delta \\ge 9.818d$. An equitable tree-$k$-coloring partitions the vertices into $k$ color classes whose sizes differ by at most one and each of which induces a forest. This replaces an earlier exponential condition on $\\Delta$ with a linear one, extending the conjecture to a much larger family of sparse graphs. The authors also note that a more careful version would allow $k \\ge \\Delta/2$, improving the stated bound for even maximum degree.","feed_headline":"Low-degeneracy graphs satisfy the equitable tree-coloring conjecture","feed_subtitle":"For d-degenerate graphs with max degree at least 9.818d, balanced forest colorings always exist.","key_machinery":"The central object is the equitable tree-$k$-coloring: a partition of the vertex set into $k$ classes, no two differing in size by more than one, each class inducing a forest. The proof's engine is an induction that isolates the $\\mu$ highest-degree vertices, colors them first, then extends the coloring to the remaining vertices one at a time while preserving balance and acyclicity. The auxiliary directed graph $H$ has the current color classes as vertices, with an edge $X \\to Y$ when a vertex in $X$ outside the initially colored set has at most one neighbor in $Y$; following such edges lets the algorithm 'switch witnesses' and move vertices along paths to free a small class. Two numerical contradictions close the proof: in the first half of the vertex order, the degree-ordering lemma from [11] bounds the failed vertex's degree and forces $\\Delta < 8.789d$, and in the second half, edge-counting yields $\\Delta/d < (\\lambda-2)(\\lambda+1.1362)/(\\lambda-3)$ with maximum below $9.818$. The parameter $\\lambda = 1 + t/s(t)$, with $s(t)=1$ for $3\\le t\\le 6$ and $s(t)=\\lceil t/5 \\rceil$ for $t\\ge 7$, controls the split point $\\mu$ and the inequalities, and the constant $9.818$ is the optimized threshold at which both contradictions bite.","core_discovery":"The paper's central claim is Theorem 1.5: every $d$-degenerate graph with maximum degree at most $\\Delta$ is equitably tree-$k$-colorable for every integer $k \\ge (\\Delta+1)/2$, as long as $\\Delta \\ge 9.818d$. Here $d$-degenerate means every subgraph contains a vertex of degree at most $d$, and an equitable tree-$k$-coloring is a balanced vertex partition into $k$ classes each inducing a forest. The proof is by induction on the number of vertices: it adds a copy of $K_r$ so that the total number of vertices is divisible by $k$, fixes a rainbow coloring of that copy, and then colors the remaining vertices one by one, allowing recoloring along paths in an auxiliary digraph of color classes. Failure of the procedure is shown to force contradictory inequalities—one producing $\\Delta < 8.789d$ in the early-failure case, the other producing $\\Delta/d < (\\lambda-2)(\\lambda+1.1362)/(\\lambda-3)$ with maximum below $9.818$ in the late-failure case. Thus the theorem confirms the conjecture for every graph whose degeneracy is at most about one tenth of its maximum degree.","pith_inferences":["The constant 9.818 is an artifact of the proof's estimates, not a structural boundary for the conjecture; the slack visible in the two contradiction inequalities suggests the ratio could be lowered substantially by sharper optimization.","The argument makes the degree-ordering lemma from [11] the true bottleneck: any attack on the full conjecture for all $d$-degenerate graphs will likely need a stronger ordering statement or a way to avoid depending on it.","The same reduction to $G\\cup K_r$ with a fixed rainbow coloring and a tracked remainder $r$ could apply to other equitable partition problems where each color class must avoid a specified finite family of forbidden subgraphs, since the rainbow-coloring trick is not specific to forests."],"forward_implications":["If Theorem 1.5 is correct, the Equitable Vertex Arboricity Conjecture holds for every graph with maximum degree Δ and degeneracy d satisfying Δ ≥ 9.818d, i.e., for all graphs whose degeneracy is at most about Δ/9.818.","The earlier exponential condition Δ ≥ 2·3^{d-1}-1 is replaced by a linear condition, so for d ≥ 4 the family of graphs known to satisfy the conjecture expands substantially.","For any graph in this class, the equitable vertex arboreal threshold is at most ⌈(Δ+1)/2⌉: there is a balanced forest coloring for every number of colors from that point upward, not just for one particular k.","The proof's remark, if made precise, would lower the requirement to k ≥ Δ/2, improving the conjecture's bound for graphs of even maximum degree in the non-exceptional cases.","Because the proof colors vertices one by one with a recoloring procedure, it provides a constructive way to produce such a balanced forest coloring whenever the degree conditions hold."],"supporting_citations":[{"why":"Supplies the degree-ordering lemma (Lemma 2.2) that bounds deg_G(v_i) and anchors every later degree estimate in the induction.","marker":"[11]"},{"why":"Gives the prior exponential lower bound on Δ for d-degenerate graphs and the planar result that Theorem 1.5 improves to a linear condition.","marker":"[8]"},{"why":"Introduces equitable tree-coloring and the Equitable Vertex Arboricity Conjecture that the paper targets.","marker":"[17]"}],"fun_headline_variants":["Equitable arboricity conjecture holds for low-degeneracy graphs","Low-degeneracy graphs get balanced forest colorings","Balanced forest partitions exist for d-degenerate graphs","Equitable tree-coloring proven when degeneracy is low"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof rests on an unproved lemma from [11]: in a $d$-degenerate graph on $n$ vertices ordered from highest to lowest degree, the $i$-th vertex has degree less than $d(1+n/i)$; if that ordering bound fails, the induction's degree estimates and both contradiction cases collapse.","fun_headline_variants_meta":{"raw":{"variants":["Equitable arboricity conjecture holds for low-degeneracy graphs","Low-degeneracy graphs get balanced forest colorings","Balanced forest partitions exist for d-degenerate graphs","Equitable tree-coloring proven when degeneracy is low"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000699,"raw_usage":{"total_tokens":3147,"prompt_tokens":926,"completion_tokens":2221,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":2154}},"tokens_in":542,"tokens_out":2221,"duration_ms":15557,"temperature":1.0,"reasoning_tokens":2154,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:24:16.168490+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a $d$-degenerate graph with maximum degree $\\Delta \\ge 9.818d$ that is not equitably tree-$k$-colorable for $k = \\lceil(\\Delta+1)/2\\rceil$; the paper predicts no such graph exists, so any counterexample found would disprove Theorem 1.5. A direct check of the load-bearing ordering lemma—comparing $\\deg_G(v_i)$ with $d(1+n/i)$ in every $d$-degenerate graph—is a more localized experiment that would test the proof's foundation even if the theorem itself still held.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the degree-ordering lemma (Lemma 2.2) that bounds deg_G(v_i) and anchors every later degree estimate in the induction."},{"cited_title":"Esperet, L","cited_arxiv_id":null,"evidence_quote":"Gives the prior exponential lower bound on Δ for d-degenerate graphs and the planar result that Theorem 1.5 improves to a linear condition."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces equitable tree-coloring and the Equitable Vertex Arboricity Conjecture that the paper targets."}],"review_version":1}