Equitable vertex arboricity conjecture holds for graphs with low degeneracy

Bei Niu; Bi Li; Xin Zhang; Yan Li

Equitable vertex arboricity conjecture holds for graphs with low degeneracy

T0 review · 0 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 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…

desk verdict Solid proof of a linear degeneracy threshold for equitable vertex arboricity; the main caveat is an unproved external lemma and a decimal constant. read the letter →

arxiv 1908.05066 v3 pith:FXMQDO4W submitted 2019-08-14 math.CO cs.DM

Xin Zhang , Bei Niu , Yan Li , Bi Li This is my paper · ORCID

classification math.COcs.DM MSC 05C15

keywords equitabletree-coloringvertexarboricitycoloringd-degenerategraphdegeneracymaximumdegreeConjecture

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

Dear Colleague,

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

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

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

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

Best,

Referee Report

0 major / 4 minor

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

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.

minor comments (4)

[§2, equations (2.22)–(2.23)] 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.
[§2, paragraph after (2.23)] 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.
[§2, Subcase 2.2] 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.
[Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof of Theorem 1.5 rests on an external degeneracy lemma and internal inequalities, not on self-citation or fitted inputs.

full rationale

The paper proves Theorem 1.5 by induction, reducing the equitable tree-k-coloring of G to an equitable coloring of G ∪ Kr, then running a recoloring algorithm. The key external input is Lemma 2.2 (Kostochka and Nakprasit [11]), cited without proof, which is used to obtain μ < n/(λ−1) and the degree bounds in (2.13) and (2.20). This is an external published lemma, not a result of the present authors, and it does not assume the target theorem. The proof then derives contradictions in Case 1 and Case 2 using only counting inequalities, convexity estimates, and the numerical assumption Δ ≥ 9.818d; no parameter is fitted to the target conclusion, and no quantity called a prediction is constructed from the data. The self-citations in the introduction and closing remarks (e.g., [18], [19], [22], [23], and [13], [15] in the remarks) provide background and open-problem context but are not load-bearing: deleting them would not affect the induction or the recoloring argument. The paper also explicitly distinguishes its proof from Theorem 2.1 of Kostochka and Nakprasit, so it is not renaming a known result. The main external dependency to verify is Lemma 2.2, and a minor wording issue about r ≥ 3 is repairable; neither constitutes circularity. No circular step meeting the quoted-equation standard was found.

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

The central proof rests on a standard lemma from the literature (Kostochka-Nakprasit) plus the choice of the numerical threshold 9.818d. No new entities or empirically fitted parameters are introduced. The theorem is a universal statement about finite graphs, so the standard axioms of finite graph theory apply.

free parameters (1)

Degeneracy ratio threshold 9.818 = 9.818
Introduced ad hoc to make the inequalities in the proof work; the proof uses bounds such as f(β)<8.789 and θ(4.1818)<9.81792 to derive the contradiction, so any constant strictly larger than θ's maximum on the relevant interval would suffice.

assumptions (1)

domain assumption Kostochka-Nakprasit Lemma 2.2 (degree bound in d-degenerate graphs)
Invoked to derive μ < n/(λ-1) and inequalities (2.13) and (2.20). It is cited from [11] and not proved in this paper; if it fails, the ordering argument and the degree bounds collapse.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Equitable vertex arboricity conjecture holds for graphs with low degeneracy." pith.science (2026). https://pith.science/paper/FXMQDO4W

@misc{pith2026190805066,
  author       = {Pith},
  title        = {Pith review of: Equitable vertex arboricity conjecture holds for graphs with low degeneracy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FXMQDO4W}},
  note         = {Machine review of arXiv:1908.05066}
}

abstract

The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations. Namely, an equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one. In this paper, we show some theoretical results on the equitable tree-coloring of graphs by proving that every $d$-degenerate graph with maximum degree at most $\Delta$ is equitably tree-$k$-colorable for every integer $k\geq (\Delta+1)/2$ provided that $\Delta\geq 9.818d$, confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Abu-Ata, F

M. Abu-Ata, F . F . Dragan. Metric tree-like structures in real-world networks: an empirical study .Networks 67(1) (2016) 49–68

work page 2016
[2]

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

work page 2008
[3]

Chartrand, H

G. Chartrand, H. V . Kronk. The point-arboricity of planar gr aphs. J. London Math. Soc. 44 (1969) 612–616

work page 1969
[4]

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

work page 2017
[5]

Drgas-Burchardt, J

E. Drgas-Burchardt, J. Dybizba ´ nski, H. Furma ´ nczyk, E. Sidorowicz, Equitable list vertex colourability and arboricity of grids. Filomat 32:18 (2018) 6353–6374

work page 2018
[6]

Drgas-Burchardt, H

E. Drgas-Burchardt, H. Furma ´ nczyk, E. Sidorowicz, Equitable improper choosability of graphs. Theoret. Comput. Sci. 844 (2020) 34–45

work page 2020
[7]

Drgas-Burchardt, H

E. Drgas-Burchardt, H. Furma ´ nczyk, E. Sidorowicz, Equitable d-degenerate Choosability of Graphs. L. Ga ¸sieniec et al. (Eds.): IWOCA 2020, Lect. Notes Comput. Sci. 12126 (2020) 251-–263

work page 2020
[8]

Esperet, L

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

work page 2015

Show all 23 references

[9]

He, R.-X

S. He, R.-X. Hao, L. Zuo. The linear ( n − 1)-arboricity of some lexicographic product graphs. Appl. Math. Comput, 338 (2018), 152–163

2018
[10]

H. Kaul, J. A. Mudrock, M. J. Pelsmajer, On equitable list a rboricity of graphs. arXiv:2008.08926 [math.CO]

2008 arXiv
[11]

A. V . Kostochka, K. Nakprasit. Equitable colourings ofd-degenerate graphs. Combin. Probab. Comput. 12 (2003) 53–60

2003
[12]

H. Lei, T . Li, Y. Ma, H. Wang. Analyzing lattice networks throu gh substructures. Appl. Math. Comput 329 (2018) 297– 314

2018
[13]

B. Li, X. Zhang, Tree-coloring problems of bounded treewi dth graphs. J. Comb. Optim. 39(1) (2020) 156–169

2020
[14]

F . Li, Q. Zhang, T . Gu, R. Dong. Optimal representation for w eb and social network graphs based on K-2-tree. IEEE Access 7 (2019) 52945–52954

2019
[15]

Y. Li, X. Zhang, Equitable list tree-coloring of bounded tre ewidth graphs. Theoret. Comput. Sci. 855 (2021) 61–67

2021
[16]

T . Miao, A. Chen, Y. Xu. Optimal structure of damaged tree- like branching networks for the equivalent thermal con- ductivity . Int. J. Therm. Sci. 102 (2016) 89–99

2016
[17]

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

2013
[18]

Zhang, B

X. Zhang, B. Niu, Equitable partition of graphs into induced lin ear forests. J. Comb. Optim. 39(2) (2020) 588–581

2020
[19]

Zhang, B

X. Zhang, B. Niu, Equitable tree- O(d)-coloring of d-degenerate graphs. arXiv:1908.05069 [math.CO]

1908 arXiv
[20]

Zhang, J.-L

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

2014
[21]

Zhang, Equitable list point arboricity of graphs

X. Zhang, Equitable list point arboricity of graphs. Filomat 30:2 (2016) 373–378

2016
[22]

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

2015
[23]

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

2016

Pith tools

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

[1] [1]

Abu-Ata, F

M. Abu-Ata, F . F . Dragan. Metric tree-like structures in real-world networks: an empirical study .Networks 67(1) (2016) 49–68

work page 2016

[2] [2]

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

work page 2008

[3] [3]

Chartrand, H

G. Chartrand, H. V . Kronk. The point-arboricity of planar gr aphs. J. London Math. Soc. 44 (1969) 612–616

work page 1969

[4] [4]

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

work page 2017

[5] [5]

Drgas-Burchardt, J

E. Drgas-Burchardt, J. Dybizba ´ nski, H. Furma ´ nczyk, E. Sidorowicz, Equitable list vertex colourability and arboricity of grids. Filomat 32:18 (2018) 6353–6374

work page 2018

[6] [6]

Drgas-Burchardt, H

E. Drgas-Burchardt, H. Furma ´ nczyk, E. Sidorowicz, Equitable improper choosability of graphs. Theoret. Comput. Sci. 844 (2020) 34–45

work page 2020

[7] [7]

Drgas-Burchardt, H

E. Drgas-Burchardt, H. Furma ´ nczyk, E. Sidorowicz, Equitable d-degenerate Choosability of Graphs. L. Ga ¸sieniec et al. (Eds.): IWOCA 2020, Lect. Notes Comput. Sci. 12126 (2020) 251-–263

work page 2020

[8] [8]

Esperet, L

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

work page 2015