REVIEW 6 minor 9 references
Equitable partition of graphs into induced linear forests
T0 review · 0 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Every finite simple graph G can be equitably partitioned into k subsets, each inducing a linear forest, for every k ≥ max{ceil((Δ(G)+1)/2), ceil(|G|/4)}.
desk verdict A sound, constructive proof of a new equitable linear arboricity bound; worth sending to a referee despite minor presentation blemishes. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the complement graph $\overline{G}$. In the dense case, $\Delta(G) \ge (|G|-1)/2$, Lemmas 2.1–2.5 convert the minimum degree of $\overline{G}$ into long paths and a matching inside $\overline{G}$; in particular Lemma 2.5 produces two vertex-disjoint $\overline{G}$-paths of lengths $\delta(\overline{G})$ and $\delta(\overline{G})+1$. Cutting these paths into blocks of four consecutive vertices, and pairing leftover vertices with complement-matching edges, yields the equitable color classes: consecutive vertices on a $\overline{G}$-path are nonadjacent in G, so each block induces a disjoint union of paths in G. In the sparse case $\Delta(G) < (|G|-1)/2$, the same complement viewpoint gives $\delta(\overline{G}) \ge |G|/2$, so Dirac's theorem supplies a Hamiltonian cycle in $\overline{G}$, which can be split into subpaths on one to four vertices and used directly as the color classes.
What would settle it
Run an exhaustive computer search over all simple graphs on up to eleven vertices, checking for each graph G and each integer k ≥ max{ceil((Δ(G)+1)/2), ceil(|G|/4)} whether V(G) admits an equitable partition into k induced linear forests; any failure refutes Theorem 3.2. A narrower check targets Lemma 2.1: search for a connected graph with minimum degree δ that contains no path of length 2δ, since that path is the source of the matching in the dense case.
Extended reading notes
Core claim
The paper's central claim is that the equitable linear vertex arborability threshold obeys $\mathrm{lva}^{\equiv}(G) \le \max\{\lceil(\Delta(G)+1)/2\rceil, \lceil |G|/4\rceil\}$ for every finite simple graph G. Equivalently, for every k at least that maximum, V(G) splits equitably into k subsets each inducing a linear forest. The proof separates two regimes. When $\Delta(G) \ge (|G|-1)/2$, it works in the complement graph $\overline{G}$: lemmas on long paths and matchings in $\overline{G}$ provide blocks of three or four vertices that are path-forests in G. When $\Delta(G) < (|G|-1)/2$, Dirac's theorem gives a Hamiltonian cycle in $\overline{G}$, which is cut into paths of length at most four. Complete graphs show the bound is sharp for the degree term.
Load-bearing premise
The dense-case proof rests on Lemma 2.1, which asserts that every connected graph with smallest degree $\delta$ contains a path of length $2\delta$; the matching built from that path is what produces the three- and four-vertex color classes, so if that lemma failed the construction would collapse.
Editorial extensions
If this is right
- For every graph G, $\mathrm{lva}^{\equiv}(G) \le \max\{\lceil(\Delta(G)+1)/2\rceil, \lceil|G|/4\rceil\}$, so a single formula bounds the equitable linear vertex arborability threshold of all graphs.
- The Equitable Vertex Arboricity Conjecture holds, in the stronger path-forest version, for every graph with $\Delta(G) \ge (|G|-1)/2$.
- Complete graphs $K_n$ attain $\lceil(\Delta+1)/2\rceil = \lceil n/2\rceil$, so the maximum-degree term in the bound cannot be lowered in general.
- In the sparse regime the constructed color classes have size at most four, so the theorem supplies partitions whose parts are both balanced and uniformly small.
Reading between the lines
- The proof uses only color-class blocks of size at most four, so a natural testable extension is whether the same partition method works with blocks of size up to m, replacing $\lceil|G|/4\rceil$ by $\lceil|G|/m\rceil$.
- The dense-case construction shows the obstruction is a matching problem in the complement, so graphs whose complements have a large matching may satisfy the partition conclusion even when the stated degree condition fails.
- A route the paper leaves implicit: for graphs with small maximum degree, the $|G|/4$ term dominates, and the Hamiltonian-cycle argument suggests the true threshold for such graphs may track Hamiltonicity of the complement rather than maximum degree.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that for every graph G and every integer k ≥ max{ceil((Δ(G)+1)/2), ceil(|G|/4)}, the vertex set of G can be equitably partitioned into k subsets, each inducing a linear forest. Theorem 1.3 establishes this under the hypothesis Δ(G) ≥ (|G|-1)/2 via a constructive three-case proof: Case 1 handles k ≥ |G|/2 with classes of size at most two; Case 2 uses a matching in the complement to form triples and pairs; Case 3 uses two disjoint paths in the complement and a detailed block construction yielding classes of sizes three and four. Lemma 3.1 removes the degree hypothesis by applying Dirac's theorem to the complement when Δ(G) < (|G|-1)/2, splitting the resulting Hamiltonian cycle into subpaths of sizes differing by at most one. Combining the two yields Theorem 3.2, an unconditional bound on the equitable linear vertex arborable threshold. The introduction also corrects a mis-attribution in the literature concerning a previous claim about the Equitable Vertex Arboricity Conjecture.
Significance. If correct, the paper confirms the Equitable Vertex Arboricity Conjecture for all graphs with Δ ≥ (|G|-1)/2 and, more generally, gives the unconditional bound lva≡(G) ≤ max{ceil((Δ+1)/2), ceil(|G|/4)}. The proof is elementary, self-contained, and constructive: all supporting lemmas are proved in the paper, and the only external result is Dirac's theorem. The bound is sharp for complete graphs, for which lva≡(K_n) = ceil(n/2). The paper also performs a useful service by pointing out that a previously cited confirmation of Conjecture 1.1 for Δ ≥ |G|/2 actually concerned the parameter va= rather than va≡; the new result supersedes that claim. The delicate Case 3 arithmetic, including the index ranges and the count |S| = μ, is carefully executed and correct.
minor comments (6)
- [Section 2, Case 1] The proof does not cover k > |G|: when k exceeds |V(G)|, one cannot partition the vertices into k nonempty subsets each of size one or two. Since the theorem is stated for all k above the threshold, please add the trivial step that if k ≥ |G|, each vertex is placed in its own class and the remaining classes are left empty; then assume k < |G|.
- [Lemma 3.1] The final split of the Hamiltonian cycle into k subpaths on one or two vertices is also not valid as written when k > |G|. The same empty-class convention should be allowed, or the proof should first reduce to the case k ≤ |G|.
- [Lemma 2.3] The parenthetical claim that the maximum neighbor index i 'is exactly the degree of v0' is false in general (e.g., a vertex with two neighbors at indices 5 and 7 has degree 2 but i = 7). The subsequent inequality i ≥ δ(G) is all that is needed, and it follows because the neighbor indices are δ(G) distinct positive integers.
- [Section 2, Case 3] The application of Lemma 2.5 requires δ(Gc) ≥ 2, but this is not stated or justified. It follows from the case assumptions, since δ(Gc) = |G|-1-Δ(G) ≥ |G|-2k > |G|/3 ≥ 1, so δ(Gc) ≥ 2; please include this.
- [Section 2, Case 3] The sentence 'Since the graph induced by V1_i or V2_i or W1_i or W2_i induce a linear forest in G' is asserted without support. For the four-vertex sets, four consecutive vertices of a path in Gc induce in G the complement of P4, which is a path; for the three-vertex W sets, the consecutive pair from Gc is a non-edge in G, so no triangle can appear. A one-sentence justification would improve the exposition.
- [Notations and Lemma 3.1] There are a few minor presentation issues: 'completement graph' should be 'complement graph', 'spit the proof' should be 'split the proof', and the proof of Lemma 3.1 should explicitly note that the hypothesis Δ(G) < (|G|-1)/2 implies |G| ≥ 3, so Dirac's theorem applies.
Circularity Check
No significant circularity: the theorem is proved from self-contained lemmas with only standard external tools.
full rationale
The paper's derivation is self-contained and non-circular. Theorem 1.3 is established constructively using Lemmas 2.1–2.5, all of which are proved in the paper from first principles (longest-path and cycle arguments). The only external result invoked is Dirac's theorem, used in Lemma 3.1 under the explicit degree condition δ(G^c) ≥ |G^c|/2, which is exactly Dirac's hypothesis; this is a standard benchmark, not an import of the target result. The color classes in Case 2 and Case 3 are built directly from matchings and paths in the complement graph, and the argument verifies by computation that the required number and sizes of parts match k and the equitable-partition condition. No parameter is fitted to the conclusion, and no 'prediction' is equivalent by construction to an input. Self-citations to [4]–[8] occur only in the introduction as historical context and motivation, and are not load-bearing in the proofs of Theorem 1.3, Lemma 3.1, or Theorem 3.2. The minor edge-case note that Dirac's theorem is unnecessary for n = 2 in Lemma 3.1 does not affect the argument's substance or introduce circularity.
Assumptions & free parameters
assumptions (3)
- standard math Dirac's theorem: a graph on n vertices with minimum degree at least n/2 has a Hamiltonian cycle.
- standard math Longest path properties in finite graphs, including that all neighbors of an endpoint lie on the longest path.
- domain assumption Graphs are finite and simple.
Cite this review
Pith. "Pith review of Equitable partition of graphs into induced linear forests." pith.science (2026). https://pith.science/paper/HGY2NDCM
@misc{pith2026190805075,
author = {Pith},
title = {Pith review of: Equitable partition of graphs into induced linear forests},
year = {2026},
howpublished = {\url{https://pith.science/paper/HGY2NDCM}},
note = {Machine review of arXiv:1908.05075}
}
abstract
It is proved that the vertex set of any simple graph $G$ can be equitably partitioned into $k$ subsets for any integer $k\geq\max\{\big\lceil\frac{\Delta(G)+1}{2}\big\rceil,\big\lceil\frac{|G|}{4}\big\rceil\}$ so that each of them induces a linear forest.
Reference graph
Works this paper leans on
-
[1]
J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, GTM 244, 2008
work page 2008
-
[2]
B.-L. Chen, K.-W. Lih, P.-L. Wu, Equitable coloring and the maximum degree, European Iournal of Combinatorics, 15 (1994) 443-447
work page 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
work page 2017
-
[4]
L. Esperet, L. Lemoine, F. Maffray. Equitable partition of graphs into induced forests. Discrete Math. 338 (2015) 1481--1483
work page 2015
-
[5]
B. Niu, X. Zhang, Y. Gao. Equitable partition of plane graphs with independent crossings into induced forests. arXiv:1903.08337 [math.CO]
work page Pith review arXiv 1903
-
[6]
X. Zhang, J.-L. Wu, A conjecture on equitable vertex arboricity of graphs, Filomat, 28:1 (2014) 217--219
work page 2014
-
[7]
J.-L. Wu, X. Zhang, H. Li. Equitable vertex arboricity of graphs. Discrete Math. 313 (23) (2013) 2696--2701
work page 2013
-
[8]
X. Zhang. Equitable vertex arboricity of planar graphs. Taiwanese J. Math 19 (1) (2015) 123--131
work page 2015
Show all 9 references
-
[9]
X. Zhang. Equitable vertex arboricity of subcubic graphs. Discrete Math. 339 (2016) 1724--1726
2016
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.