{"id":"b94bc236-a264-4867-957b-c19be7988220","arxiv_id":"1908.05069","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Every d-degenerate graph with at least beta-Delta vertices has an equitable tree-k-coloring for every k at least alpha-d, for twelve explicit (alpha, beta) pairs such as (8,56) and (52,6).","lead":"This paper proves that for a large class of sparse graphs, the vertices can be divided into almost equally sized groups, each containing no cycles, using a number of colors that grows only linearly with the graph's sparseness. It replaces an exponential bound for this coloring problem and gives twelve explicit size-versus-degree tradeoffs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof establishes only that every color class has at most t=ceil(n/k) vertices; this does not imply equitability.","rationale":"The reader's verdict was CONDITIONAL based on two presentation errors, and their weakest_assumption concerned the counting chain in Claim 2. My stress-test found a more fundamental gap: the proof's definitional equivalence between 'equitable' and 'every color class has size at most ceil(n/k)' is false, and the argument's final step relies directly on that false equivalence. The auxiliary digraph and switching procedure in Claim 2 are designed to keep every color class within an upper bound L_i, not to enforce a lower bound. Consequently, after coloring all vertices, the proof only guarantees that each class has at most t vertices. Since n can satisfy k(t-1)<n with deficits distributed unevenly, class sizes such as {8,10,10} for n=28,k=3 are compatible with the proof's conditions but violate equitability. This is not a minor typo; it means the central claim of the paper is not established by the submitted proof. The theorem could still be true, but the manuscript would need a substantial addition to prove the missing lower-bound condition. Therefore the verdict should be REJECT for the current proof, rather than CONDITIONAL.","tokens_in":9162,"tokens_out":60090,"duration_ms":521559,"concrete_test":"Test the claimed equivalence directly: for n=28 and k=3, the multiset {8,10,10} satisfies max class size = 10 = ceil(28/3), yet the classes differ by 2 and are not equitable. Then scan the proof of Claims 1 and 2 for any invariant of the form |c^{-1}(i)| >= floor(n/k) or >= t-1; no such lower bound appears. If none exists, the final inference in Section 2 is invalid and the proof requires an additional balancing argument.","verdict_should_be":"REJECT","load_bearing_attack":"Section 1 states that an equitable tree-k-coloring is 'equivalently' a tree-k-coloring with each color class of size at most ceil(|G|/k). This equivalence is false: for n=28 and k=3, class sizes 8,10,10 all satisfy the bound but differ by 2, so the coloring is not equitable. The proof then concludes at the end of Section 2 that because H_{m+1}=G has every color class of size at most L_{m+1}=t=ceil(n/k), it is equitable. This conclusion does not follow. Claims 1 and 2 maintain only upper bounds L_i on color class sizes. The switching argument moves excess along a directed path and adds one vertex to some class in Y0, but nothing forces every class to end with size at least t-1. Thus the proof establishes a tree-k-coloring with all classes of size at most t, not the required equitable coloring. The theorem may be true, but the argument as written does not prove it.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proves Theorem 1.1: for each pair (α, β) in the table {(8,56), (9,26), (10,18), (11,15), (12,13), (13,12), (14,11), (15,10), (17,9), (20,8), (27,7), (52,6)}, every d-degenerate graph G with maximum degree at most Δ and order n ≥ βΔ is equitably tree-k-colorable for every k ≥ αd. The proof starts with a greedy coloring in a degenerate ordering and shows that if t = ceil(n/k) is at most β(2 − 1/α), the greedy procedure produces a tree-k-coloring in which every color class has at most t vertices. For larger t, the proof partitions V(G) into blocks C_i using a 3-ary expansion of t, colors the blocks sequentially, and maintains upper bounds L_i on color-class sizes; an auxiliary digraph and a switching operation are used to show that a suitable color class is always available. The final line asserts that because every color class of H_{m+1} = G has at most L_{m+1} = t vertices, the coloring is equitable.","tokens_in":9313,"tokens_out":33077,"duration_ms":295929,"significance":"If Theorem 1.1 were established, it would be a substantial improvement over the exponential 3^{d−1} bound of Esperet, Lemoine and Maffray, and it would partially improve the result of Chen et al. for graphs with sufficiently large order relative to maximum degree. The proof is self-contained and the auxiliary-digraph switching argument is a nontrivial technique that could be useful in future work. However, the argument as written does not prove equitability: it shows only that every color class has size at most ceil(n/k), a condition strictly weaker than the definition of an equitable coloring. The main theorem is therefore not established by this manuscript.","major_comments":[{"comment":"The statement in Section 1 that an equitable tree-k-coloring is 'equivalently' a tree-k-coloring with each color class of size at most ceil(|G|/k) is false. For example, with n = 28 and k = 3, the class sizes 8, 10, 10 all satisfy the upper bound 10, but the largest and smallest classes differ by 2, so the coloring is not equitable. The proof's Claims 1 and 2 maintain only upper bounds L_i on color-class sizes, and the switching operation never forces any class to have size at least t − 1. Consequently, the final conclusion 'This just gives an equitable tree-k-coloring of G' does not follow from the preceding inequalities. The greedy case at the beginning of Section 2 has the same defect, as it also concludes equitability from an upper-bound invariant.","section":"Section 1 and the end of Section 2"},{"comment":"The displayed inequality (2.15) places k in the denominator of the first term: (6α−12)/((2α−5)β k). Substituting Δ ≤ n/β ≤ kt/β gives (6α−12)k/((2α−5)β), with k in the numerator. The subsequent bound (2.17) is consistent with the corrected version, and for (α, β) = (8, 56) the corrected inequality gives k/d approximately 7.99, contradicting k ≥ 8d. Nevertheless, as printed, the derivation of (2.17) from (2.15) is invalid and the equation must be corrected.","section":"Equation (2.15)"}],"minor_comments":[{"comment":"The word 'incudes' in the abstract should be 'induces'.","section":"Abstract"},{"comment":"The expression 'l_m/t = l_m/l_{m1} ≤ 1/3' contains a typo: the second denominator should be l_{m+1}, not l_{m1}.","section":"After equation (2.16)"},{"comment":"The proof uses Δ as if it were Δ_0, but only Δ_1, Δ_2, ... are defined; it would be clearer to define Δ_0 = Δ explicitly.","section":"Proposition 1"},{"comment":"It should be stated explicitly that the coloring order inside each C_i is a degenerate ordering of the induced subgraph G[C_i], distinct from the maximum-degree-first order used to define the partition; otherwise the bound 'at most d already-colored neighbors in C_i' is not justified.","section":"Section 2, partition construction"}],"recommendation":"reject","confidential_remarks":"The main theorem is not established because the proof establishes only a tree-k-coloring with all color classes of size at most ceil(n/k), which is strictly weaker than equitability. The false equivalence in Section 1 is a fundamental gap that cannot be repaired by local edits; a substantially new invariant or argument would be needed. The typo in (2.15) is repairable, but it does not affect the primary concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things up front. The claimed theorem is a real target: it replaces the exponential 3^(d-1) bound of Esperet-Lemoine-Maffray with a linear O(d) bound for d-degenerate graphs when n >= beta*Delta. And the proof as written does not prove it. The stress-test note is correct. The equivalently statement in Section 1 is false: for n=28, k=3, class sizes 8,10,10 all satisfy the at-most-ceil(n/k) bound but are not equitable. The entire construction then runs on upper bounds only. Claims 1 and 2 maintain at-most-L_i per class, the switching argument moves one vertex along a path to an underfull class, and the end of Section 2 concludes that because every class has at most t=ceil(n/k), the coloring is equitable. That conclusion needs a lower bound on every class; nothing in the proof gives one. Since n>k(t-1), at least one class must reach t, but the rest can sit at t-2 or below and still satisfy the at-most-t condition. So this is a load-bearing gap, not a typo. What the paper does well: the technique is genuinely interesting. The construction partitions vertices into blocks whose sizes are ternary-scaled, and the auxiliary digraph plus switching is a real adaptation of Kostochka-Nakprasit-Pemmaraju. Proposition 1's weighted degree bound and the (alpha,beta) table show real care. I checked the arithmetic in the table and the final contradiction as far as I could by hand; it is consistent. There is also no circularity: prior work is cited for technique, not as an input. The citation pattern is honest. Soft spots in proportion: the equitability gap is severe. Separate from that, there are two small presentation issues - the initial small-t inequality is sloppy, and (2.15) has a denominator that disagrees with the derivation in (2.17)/(2.18). Those are minor and fixable. Bottom line: this is a promising proof of the right theorem, but the current text proves a weaker statement: existence of a tree-k-coloring with all color classes of size at most ceil(n/k). That weaker statement is not equivalent to equitability. If the authors can strengthen the argument to actually balance the classes - maybe by tracking how many classes are at t versus t-1, or by a final redistribution argument - the result is worth publishing. As it stands, I would not cite it and I would not accept it. It should still go to a serious referee. The main idea is substantial enough that a referee can point the authors to the missing lower-bound argument, and the fix may be short. Send it, but expect revision.","headline":"Nice linear-bound theorem with real technique, but the proof as written only controls color classes from above and does not prove the equitability condition.","tokens_in":729,"tokens_out":2897,"would_cite":false,"duration_ms":69329,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every d-degenerate graph with order at least βΔ is equitably tree-k-colorable for every k ≥ αd, for twelve explicit pairs (α,β).","keywords":["equitable tree-k-coloring","d-degenerate graph","equitable coloring","tree coloring","vertex arboricity","linear color bound","maximum degree","graph coloring"],"falsifier":"For $d=2$ and the first row of the table, the theorem asserts that every 2-degenerate graph with at least $56\\Delta$ vertices admits an equitable tree-16-coloring. An exhaustive search over 2-degenerate graphs with small $\\Delta$ (say 3, 4, 5) up to the required order, looking for a single graph that fails the coloring, would directly settle the claim; a cheaper numerical check is whether any listed pair actually makes the left side of inequality (2.18) exceed the right side, which would remove the contradiction and pinpoint a false case.","tokens_in":8938,"feed_emoji":"🌳","tokens_out":7640,"duration_ms":72633,"temperature":0.7,"pith_summary":"The paper proves that every $d$-degenerate graph can be colored with a number of colors linear in $d$—rather than exponential in $d$—provided the graph is large compared with its maximum degree. The coloring in question is an equitable tree-$k$-coloring: $k$ colors, each color class induces a forest, and any two color classes differ in size by at most one. Concretely, for each pair $(\\alpha,\\beta)$ in a twelve-row table, $k\\ge \\alpha d$ colors always suffice whenever the graph has at least $\\beta\\Delta$ vertices, where $\\Delta$ is the maximum degree. The result matters because it turns an exponential guarantee into a linear one for all sufficiently large degenerate graphs, bringing the theory closer to practical color counts for communication-network decomposition problems.","feed_headline":"O(d) colors suffice for equitable tree-coloring of d-degenerate graphs","feed_subtitle":"When the graph is large enough, k ≥ αd colors always give an equitable tree-coloring.","key_machinery":"The argument is carried by a block decomposition of the vertex set combined with an auxiliary digraph. Write $t=\\lceil n/k\\rceil$; the proof slices $V(G)$ into $m+1$ blocks whose sizes are governed by the base-3 digits of $t$, and builds each block so that any vertex placed in it has fewer than $(2\\alpha-4)d$ neighbors in the already constructed part. While coloring a vertex, the proof builds a digraph $D$ whose vertices are the $k$ current color classes: there is an arc $X\\to Y$ when some vertex in $X$ has at most one neighbor in $Y$, so moving vertices along directed paths rebalances class sizes without increasing the maximum class size. The decisive step is a counting bound on the number $y$ of color classes reachable from the undersized classes, which together with the $d$-degeneracy edge inequality forces $y/d<\\alpha/(2\\alpha-3)$; that bound turns an apparent room to complete the coloring into a numerical contradiction, and the listed pairs are exactly those for which the final polynomial inequality becomes impossible.","core_discovery":"The paper establishes a linear bound for equitable tree-colorings of degenerate graphs under a mild largeness condition. In the paper's own terms, the central claim is that for any $d$-degenerate graph $G$ with maximum degree at most $\\Delta$ and order $n$, if $n\\ge \\beta\\Delta$ and $k\\ge \\alpha d$, then $G$ admits an equitable tree-$k$-coloring, for every integer pair $(\\alpha,\\beta)$ in the table $(8,56), (9,26), (10,18), (11,15), (12,13), (13,12), (14,11), (15,10), (17,9), (20,8), (27,7), (52,6)$. Each color class must induce a forest and the color class sizes must differ by at most one. This replaces the prior exponential $3^{d-1}$ bound with a linear $O(d)$ bound whenever the graph is large relative to its maximum degree, and it partially sharpens known results for 5-degenerate graphs and for graphs with maximum degree at least $10d$.","pith_inferences":["The proof's arithmetic suggests the twelve listed pairs are not isolated: the same polynomial inequality likely yields a continuous curve of admissible pairs, so neighboring pairs could be computed directly from the same argument.","The largeness hypothesis $n\\ge \\beta\\Delta$ is used mainly to keep block sizes separated; removing or relaxing it would likely need a different block hierarchy, which the paper does not attempt.","The auxiliary-digraph switching technique may transfer to other balanced coloring notions beyond forests, such as equitable colorings with bounded degeneracy in each color class, whenever a similar block partition is available."],"forward_implications":["Choosing $(\\alpha,\\beta)=(8,56)$: every $d$-degenerate graph with at least $56\\Delta$ vertices is equitably tree-$k$-colorable for every $k\\ge 8d$.","Choosing $(\\alpha,\\beta)=(52,6)$: the same holds with $52d$ colors as soon as the graph has at least $6\\Delta$ vertices, giving the mildest largeness condition among the listed pairs.","The theorem partially supersedes the earlier exponential $3^{d-1}$ bound, since $\\alpha d$ grows linearly in $d$.","Together with the prior result for graphs with $\\Delta\\ge 10d$, this shows equitable tree-coloring of $d$-degenerate graphs is governed by linear rather than exponential color counts whenever the graph is large relative to $\\Delta$."],"supporting_citations":[{"why":"Supplies the prior exponential bound $k\\ge 3^{d-1}$ that this theorem improves, along with the motivating planar case.","marker":"[3]"},{"why":"Contributes the proof idea: a block construction and auxiliary digraph argument that the present proof adapts to the tree-coloring setting.","marker":"[4]"},{"why":"Introduces equitable tree-$k$-coloring and states the conjectures that motivate the search for small color counts.","marker":"[5]"},{"why":"Supplies a recent result on $d$-degenerate graphs with large maximum degree that this paper partially improves.","marker":"[6]"},{"why":"Gives the 5-degenerate case with $k\\ge (\\Delta+1)/2$, a partial antecedent generalized here.","marker":"[2]"}],"fun_headline_variants":["Linear colors for equitable tree-coloring of degenerate graphs","Exponential to linear: equitable tree-coloring of d-degenerate graphs","Equitable tree-coloring: O(d) colors for large d-degenerate graphs","Linear bound for equitable tree-coloring of d-degenerate graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires that a vertex being colored cannot have $(2\\alpha-3)d$ or more neighbors that are already colored; this boundary is set by the block-construction threshold and the $d$-degenerate edge count, and if it fails the final contradiction no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["Linear colors for equitable tree-coloring of degenerate graphs","Exponential to linear: equitable tree-coloring of d-degenerate graphs","Equitable tree-coloring: O(d) colors for large d-degenerate graphs","Linear bound for equitable tree-coloring of d-degenerate graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000516,"raw_usage":{"total_tokens":2535,"prompt_tokens":1008,"completion_tokens":1527,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":624,"completion_tokens_details":{"reasoning_tokens":1452}},"tokens_in":624,"tokens_out":1527,"duration_ms":11737,"temperature":1.0,"reasoning_tokens":1452,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:26:03.079342+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $d=2$ and the first row of the table, the theorem asserts that every 2-degenerate graph with at least $56\\Delta$ vertices admits an equitable tree-16-coloring. An exhaustive search over 2-degenerate graphs with small $\\Delta$ (say 3, 4, 5) up to the required order, looking for a single graph that fails the coloring, would directly settle the claim; a cheaper numerical check is whether any listed pair actually makes the left side of inequality (2.18) exceed the right side, which would remove the contradiction and pinpoint a false case.","supporting_citations":[],"review_version":1}