Equitable tree-$O(d)$-coloring of $d$-degenerate graphs

Bei Niu; Xin Zhang

REVIEW 2 major objections 4 minor 1 cited by

Equitable tree-$O(d)$-coloring of $d$-degenerate graphs

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

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

Pith's one-line read Every d-degenerate graph with order at least βΔ is equitably tree-k-colorable for every k ≥ αd, for twelve explicit pairs (α,β).

desk verdict 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. read the letter →

arxiv 1908.05069 v1 pith:SJS7FNDX submitted 2019-08-14 math.CO cs.DM

Xin Zhang , Bei Niu This is my paper · ORCID

classification math.COcs.DM MSC 05C15

keywords equitabletree-k-coloringd-degenerategraphcoloringtreevertexarboricitylinearcolorboundmaximumdegree

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

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$.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

Referee Report

2 major / 4 minor

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.

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 (2)

[Section 1 and the end of Section 2] 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.
[Equation (2.15)] 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.

minor comments (4)

[Abstract] The word 'incudes' in the abstract should be 'induces'.
[After equation (2.16)] 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}.
[Proposition 1] The proof uses Δ as if it were Δ_0, but only Δ_1, Δ_2, ... are defined; it would be clearer to define Δ_0 = Δ explicitly.
[Section 2, partition construction] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the proof is self-contained and none of its load-bearing steps reduce to the theorem being proved, though the final equitability inference is logically invalid as a correctness matter.

full rationale

The derivation chain in Section 2 does not use Theorem 1.1 as an input. Every contradiction is derived from d-degeneracy, the maximum degree bound, the upper-bound invariant on color-class sizes, and explicit inequalities involving the parameters alpha and beta. The cited works [3], [4], [5], and [6] are used for motivation, history, or proof technique; none supplies a load-bearing premise whose validity is assumed from the authors' own prior work. The table of (alpha,beta) pairs is introduced as a parameter choice making the final polynomial inequality (2.18) contradictory; selecting constants to force a contradiction is ordinary proof design, not fitting data and then calling the result a prediction. There is no fitted input, no self-citation chain that replaces an argument, and no renamed known result. The only significant defect is outside circularity: the opening assertion that an equitable tree-k-coloring is equivalently a tree-k-coloring with every color class of size at most ceil(|G|/k) is false, since for n=28 and k=3 the class sizes 8,10,10 all satisfy the upper bound but are not equitable. Consequently the proof as written appears to establish only a tree-k-coloring with all classes of size at most t, not the required equitability. That is a correctness gap, not a circular reduction: the target conclusion is not assumed by construction, it is merely inferred through an invalid equivalence. Thus the circularity score is 0.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

No empirical data or extra physical entities are introduced. The only hand-chosen inputs are the (alpha, beta) pairs in the theorem table, which are proof constants rather than fitted parameters.

free parameters (1)

tradeoff constants (alpha, beta) = (8,56), (9,26), (10,18), (11,15), (12,13), (13,12), (14,11), (15,10), (17,9), (20,8), (27,7), (52,6)
Hand-chosen integer pairs that make the closing inequality (2.18) contradictory; they are not estimated from data, but the proof only runs for these choices.

assumptions (3)

standard math A d-degenerate graph on v vertices has fewer than d*v edges.
Used at (2.6), (2.8), and for the bound d(|S|+|T|) > e(T,S) in Claim 2.
standard math Every induced subgraph of a d-degenerate graph is d-degenerate, so a degenerate ordering of C_i exists.
Used when coloring vertices of C_i with at most d earlier neighbors within C_i.
standard math The base-3 representation of t with digits omega_i in {0,1,2} and omega_1 nonzero exists for every positive integer t.
Defines the partition blocks A_i and B_i through the numbers l_i.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Equitable tree-$O(d)$-coloring of $d$-degenerate graphs." pith.science (2026). https://pith.science/paper/SJS7FNDX

@misc{pith2026190805069,
  author       = {Pith},
  title        = {Pith review of: Equitable tree-$O(d)$-coloring of $d$-degenerate graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SJS7FNDX}},
  note         = {Machine review of arXiv:1908.05069}
}

abstract

An equitable tree-$k$-coloring of a graph is a vertex coloring on $k$ colors so that every color class incudes a forest and the sizes of any two color classes differ by at most one.This kind of coloring was first introduced in 2013 and can be used to formulate the structure decomposition problem on the communication network with some security considerations. In 2015, Esperet, Lemoine and Maffray showed that every $d$-degenerate graph admits an equitable tree-$k$-coloring for every $k\geq 3^{d-1}$. Motivated by this result, we attempt to lower their exponential bound to a linear bound. Precisely, we prove that every $d$-degenerate graph $G$ admits an equitable tree-$k$-coloring for every $k\geq \alpha d$ provided that $|G|\geq \beta \Delta(G)$, where $(\alpha,\beta)\in \{(8,56), (9,26), (10,18), (11,15), (12,13), (13,12), (14,11), (15,10), (17,9), (20,8), (27,7), (52,6)\}$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Equitable vertex arboricity conjecture holds for graphs with low degeneracy
math.CO 2019-08 conditional novelty 6.0 of 10

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.

Reference graph

Works this paper leans on

11 extracted references · 2 canonical work pages · cited by 1 Pith paper

[1]

J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, GTM 244, 2008

2008
[2]

Chen, K.-W

B.-L. Chen, K.-W. Lih, P.-L. Wu, Equitable coloring and the maximum degree, European Iournal of Combinatorics, 15 (1994) 443-447

1994
[3]

G. Chen, Y. Gao, S. Shan, G. Wang, J.-L. Wu. Equitable vertex arboricity of 5 -degenerate graphs. J. Comb. Optim. 34(2) (2017) 426--432

2017
[4]

Esperet, L

L. Esperet, L. Lemoine, F. Maffray. Equitable partition of graphs into induced forests. Discrete Math. 338 (2015) 1481--1483

2015
[5]

B. Niu, X. Zhang, Y. Gao. Equitable partition of plane graphs with independent crossings into induced forests. arXiv:1903.08337 [math.CO]

arXiv 1903
[6]

Zhang, J.-L

X. Zhang, J.-L. Wu, A conjecture on equitable vertex arboricity of graphs, Filomat, 28:1 (2014) 217--219

2014
[7]

A. V. Kostochka, K. Nakprasit, S. V. Pemmaraju. On equitable coloring of d -degenerate graphs. SIAM J. Discrete Math. 19(1) (2005) 83--95

work page 2005
[8]

J.-L. Wu, X. Zhang, H. Li. Equitable vertex arboricity of graphs. Discrete Math. 313 (23) (2013) 2696--2701

2013

Show all 11 references

[9]

X. Zhang. Equitable vertex arboricity of planar graphs. Taiwanese J. Math 19 (1) (2015) 123--131

2015
[10]

X. Zhang. Equitable vertex arboricity of subcubic graphs. Discrete Math. 339 (2016) 1724--1726

2016
[11]

Zhang, B

X. Zhang, B. Niu, Y. Li, B. Li. Equitable vertex arboricity of d -degenerate graphs. manuscript available at \\ https://faculty.xidian.edu.cn/zhangxin/en/lwcg/371805/content/7090.htm\#lwcg

Pith tools

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

[1] [1]

J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, GTM 244, 2008

2008

[2] [2]

Chen, K.-W

B.-L. Chen, K.-W. Lih, P.-L. Wu, Equitable coloring and the maximum degree, European Iournal of Combinatorics, 15 (1994) 443-447

1994

[3] [3]

G. Chen, Y. Gao, S. Shan, G. Wang, J.-L. Wu. Equitable vertex arboricity of 5 -degenerate graphs. J. Comb. Optim. 34(2) (2017) 426--432

2017

[4] [4]

Esperet, L

L. Esperet, L. Lemoine, F. Maffray. Equitable partition of graphs into induced forests. Discrete Math. 338 (2015) 1481--1483

2015

[5] [5]

B. Niu, X. Zhang, Y. Gao. Equitable partition of plane graphs with independent crossings into induced forests. arXiv:1903.08337 [math.CO]

arXiv 1903

[6] [6]

Zhang, J.-L

X. Zhang, J.-L. Wu, A conjecture on equitable vertex arboricity of graphs, Filomat, 28:1 (2014) 217--219

2014

[7] [7]

A. V. Kostochka, K. Nakprasit, S. V. Pemmaraju. On equitable coloring of d -degenerate graphs. SIAM J. Discrete Math. 19(1) (2005) 83--95

work page 2005

[8] [8]

J.-L. Wu, X. Zhang, H. Li. Equitable vertex arboricity of graphs. Discrete Math. 313 (23) (2013) 2696--2701

2013