pith. sign in

arxiv: 2604.13606 · v1 · submitted 2026-04-15 · 🧮 math.CO

Equitable tree colouring of graphs

Yuping Gao , Allan Lo , Songling Shan This is my paper

Pith reviewed 2026-05-10 13:18 UTC · model grok-4.3

classification 🧮 math.CO
keywords equitable colouringtree colouringforest colouringmaximum degreearboricitydegenerate graphsHajnal-Szemerédi theorem
0
0 comments X

The pith

Every graph with n at least 3Δ^4 and maximum degree Δ admits an equitable tree colouring with k colours whenever k is at least (Δ+2)/2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The Hajnal–Szemerédi theorem gives a proper equitable colouring of any graph of maximum degree Δ using Δ+1 colours, with colour classes nearly equal in size. This paper examines the variant in which each colour class must induce a forest instead of an independent set. It establishes that when the number of vertices is large enough, specifically at least 3Δ^4, the same equitable property holds with far fewer colours, only about half of Δ. The result confirms a conjecture of Wu, Zhang, and Li for even Δ and comes within one colour for odd Δ, at least for all sufficiently large graphs. The paper also proves analogous statements when colour classes are required to be d-degenerate rather than forests.

Core claim

If n ≥ 3Δ^4 and k ≥ (Δ+2)/2, then every n-vertex graph G with maximum degree at most Δ admits a proper k-colouring in which each colour class induces a forest and the sizes of the colour classes differ by at most one.

What carries the argument

An equitable tree k-colouring: a proper vertex colouring using k colours such that each monochromatic subgraph is a forest and all colour classes have sizes differing by at most one.

If this is right

  • The conjecture of Wu, Zhang, and Li holds for all even Δ and all sufficiently large graphs.
  • For odd Δ the same conjecture holds up to an additive error of one colour when n is large.
  • Equitable d-degenerate k-colourings exist under the same size and degree conditions for suitable k.
  • The number of colours needed for an equitable forest colouring is at most roughly half the number required for an equitable independent-set colouring.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The polynomial lower bound on n may be improvable with a more refined counting argument or different decomposition.
  • For fixed small Δ the result could be verified directly by computer search on all graphs up to the size threshold.
  • The same technique might adapt to list-colouring or choosability versions of equitable tree colourings.

Load-bearing premise

The number of vertices must be at least 3Δ^4 for the stated bound on k to guarantee the existence of the colouring.

What would settle it

A graph with maximum degree Δ, fewer than 3Δ^4 vertices, and no equitable tree colouring using only (Δ+2)/2 colours.

read the original abstract

Let $k \in \mathbb{N}$ and let $G$ be a simple graph with maximum degree $\Delta$. A $k$-colouring $\varphi$ of $G$ is an assignment of colours from $\{1,2,\ldots,k\}$ to the vertices of $G$. We call $\varphi$ proper if adjacent vertices receive distinct colours, and equitable if the sizes of any two colour classes differ by at most one. The celebrated Hajnal--Szemer\'{e}di theorem states that a proper equitable $k$-colouring exists whenever $k \ge \Delta + 1$. In this paper, we study its tree colouring variant in which each colour class induces a forest. This is closely related to the vertex arboricity which was introduced by Chartrand, Kronk, and Wall. More precisely, we prove that if $n \ge 3\Delta^4$ and $k \ge (\Delta+2)/2$, then every $n$-vertex graph with maximum degree at most $\Delta$ contains an equitable tree $k$-colouring. This confirms a conjecture of Wu, Zhang, and Li when $\Delta$ is even and up to an additive constant of $1$ otherwise for large $n$. We also consider $d$-degenerate colouring in which each colour class induces a $d$-degenerate graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that if n ≥ 3Δ⁴ and k ≥ (Δ+2)/2, then every n-vertex graph with maximum degree at most Δ admits an equitable tree k-colouring (a k-colouring in which each colour class induces a forest and the colour classes differ in size by at most one). This confirms a conjecture of Wu, Zhang, and Li exactly when Δ is even and up to an additive constant of 1 when Δ is odd, for all sufficiently large n. The paper also considers the analogous question for d-degenerate colourings.

Significance. If correct, the result is significant: it shows that the equitable constraint can be satisfied for forest partitions without increasing the number of colours beyond the known non-equitable vertex-arboricity bound (up to the noted additive 1 for odd Δ). The polynomial threshold on n is isolated to the equitable balancing argument and does not affect the underlying non-equitable forest partition. This advances the study of relaxed equitable colourings and provides a concrete sufficient condition under which the conjecture holds.

major comments (2)
  1. [§4] §4 (proof of the main theorem): the equitable adjustment step that invokes the size condition n ≥ 3Δ⁴ is load-bearing for the final claim; the argument should explicitly verify that the initial (non-equitable) forest partition produced by the vertex-arboricity bound can always be balanced without increasing k.
  2. [Theorem 1.1] Theorem 1.1 and the statement of the conjecture: the paper claims confirmation 'up to an additive constant of 1' for odd Δ; it would strengthen the presentation to state the precise known non-equitable bound (e.g., ⌈(Δ+1)/2⌉ or equivalent) so the exact gap is visible.
minor comments (2)
  1. [Abstract] Abstract: the sentence on d-degenerate colouring is stated but no theorem or bound is given; if this direction is only a remark, the wording should indicate that the main result concerns tree colourings.
  2. [Introduction] Notation: the definition of 'tree colouring' (each colour class induces a forest) is clear, but a short reminder of the relation to vertex arboricity in the introduction would help readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and the constructive suggestions. The comments have helped us improve the clarity of our manuscript. We address each major comment below and have incorporated the suggested changes in the revised version.

read point-by-point responses

  1. Referee: [§4] §4 (proof of the main theorem): the equitable adjustment step that invokes the size condition n ≥ 3Δ⁴ is load-bearing for the final claim; the argument should explicitly verify that the initial (non-equitable) forest partition produced by the vertex-arboricity bound can always be balanced without increasing k.

    Authors: We agree with the referee that an explicit verification of this step would enhance the readability of the proof. In the revised manuscript, we have inserted a detailed explanation in Section 4, right after invoking the non-equitable forest partition theorem. This addition shows that, given n ≥ 3Δ⁴, the initial partition into k forests can be balanced by transferring a small number of vertices between classes. Since each class induces a forest and the maximum degree is Δ, there are always available vertices to move without creating cycles or violating the degree constraints, ensuring the equitable property is achieved without increasing the number of colors. revision: yes

  2. Referee: [Theorem 1.1] Theorem 1.1 and the statement of the conjecture: the paper claims confirmation 'up to an additive constant of 1' for odd Δ; it would strengthen the presentation to state the precise known non-equitable bound (e.g., ⌈(Δ+1)/2⌉ or equivalent) so the exact gap is visible.

    Authors: This is a helpful suggestion for improving the exposition. We have revised the statement of Theorem 1.1 and the surrounding discussion to explicitly state that the non-equitable vertex-arboricity is at most ⌈(Δ + 1)/2⌉. This makes the precise gap of 1 color for odd Δ immediately apparent when comparing to our equitable bound of (Δ + 2)/2. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in the proof

full rationale

The paper is a standard mathematical existence proof establishing that for n ≥ 3Δ⁴ and k ≥ (Δ+2)/2 every n-vertex graph of maximum degree Δ admits an equitable tree k-coloring. No equations, fitted parameters, or self-definitional reductions appear; the central claim is proved directly rather than obtained by renaming or re-deriving prior fitted quantities. The cited conjecture of Wu, Zhang, and Li is external prior work by different authors and is not used as a load-bearing self-citation. The polynomial size threshold is explicitly isolated as a sufficient condition for the equitable adjustment step and does not create a circular dependency with the existence of a (non-equitable) forest partition. The derivation chain is therefore self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the Hajnal-Szemerédi theorem (standard) and basic facts about forests and degeneracy; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • standard math Hajnal-Szemerédi theorem: every graph with maximum degree Δ has a proper equitable (Δ+1)-colouring
    Invoked in the abstract as the celebrated background result that the tree-colouring variant improves upon.

pith-pipeline@v0.9.0 · 5539 in / 1289 out tokens · 34660 ms · 2026-05-10T13:18:43.947858+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Chartrand, H

    G. Chartrand, H. V. Kronk, and C. E. Wall. The point-arboricity of a graph.Israel J. Math., 6:169–175, 1968

    work page 1968

  2. [2]

    B. L. Chen, K. W. Lih, and P. L. Wu. Equitable coloring and the maximum degree.European J. Combin., 15(5):443–447, 1994

    work page 1994

  3. [3]

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

    work page 2017

  4. [4]

    P. Chen, W. Liu, and X. Zhang. Equitable vertex arboricity of graphs with low maximum degree. Graphs Combin., 41(4):Paper No. 72, 9, 2025

    work page 2025

  5. [5]

    P. Erd˝ os. Problem 9.Theory of graphs and its applications, Prague: Czech Acad. Sci. Publ., page 159, 1964. 14

    work page 1964

  6. [6]

    Esperet, L

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

    work page 2015

  7. [7]

    H. Fan, H. A. Kierstead, G. Liu, T. Molla, J. L. Wu, and X. Zhang. A note on relaxed equitable coloring of graphs.Inform. Process. Lett., 111(21-22):1062–1066, 2011

    work page 2011

  8. [8]

    Hajnal and E

    A. Hajnal and E. Szemer´ edi. Proof of a conjecture of P. Erd˝ os. InCombinatorial theory and its applications, II (Proc. Colloq., Balatonf¨ ured, 1969), pages 601–623. North-Holland, Amsterdam, 1970

    work page 1969

  9. [9]

    H. A. Kierstead and A. V. Kostochka. A short proof of the Hajnal-Szemer´ edi theorem on equitable colouring.Combin. Probab. Comput., 17(2):265–270, 2008

    work page 2008

  10. [10]

    Kim, S.-I

    R. Kim, S.-I. Oum, and X. Zhang. Equitable partition of planar graphs.Discrete Math., 344(6):Pa- per No. 112351, 6, 2021

    work page 2021

  11. [11]

    Lov´ asz

    L. Lov´ asz. On decomposition of graphs.Studia Sci. Math. Hungar., 1:237–238, 1966

    work page 1966

  12. [12]

    W. Meyer. Equitable coloring.Amer. Math. Monthly, 80:920–922, 1973

    work page 1973

  13. [13]

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

    work page 2013

  14. [14]

    Zhang and X

    H. Zhang and X. Zhang. Theoretical aspects of equitable partition of networks into sparse modules. Theoret. Comput. Sci., 871:51–61, 2021

    work page 2021

  15. [15]

    Zhang, B

    X. Zhang, B. Niu, Y. Li, and B. Li. Equitable vertex arboricity conjecture holds for graphs with low degeneracy.Acta Math. Sin. (Engl. Ser.), 37(8):1293–1302, 2021

    work page 2021

  16. [16]

    Zhang and J

    X. Zhang and J. L. Wu. A conjecture on equitable vertex arboricity of graphs.FILOMAT, 28:217– 219, 2014. 15

    work page 2014