Equitable tree colouring of graphs
Yuping Gao, Allan Lo, Songling Shan · 2026
Read Equitable tree colouring of graphs by Yuping Gao, Allan Lo, Songling Shan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-13606.txt.
Introduction
Gao, Lo, and Shan study equitable tree colouring. Each colour class must form a forest. Class sizes differ by at most one. Extending the Hajnal-Szemeredi theorem to this forest setting, they prove such a colouring exists for large graphs of bounded maximum degree. The colour count must clear roughly half the degree plus one. The result settles a conjecture by Wu, Zhang, and Li for even degree. For odd degree it misses by at most one colour.
Catalog record
| CREATOR | Yuping Gao, Allan Lo, Songling Shan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49079 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.13606
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Equitable tree colouring of graphs Yuping Gao, Allan Lo, Songling Shan Abstract Let k ∈ ℕ k\in\mathbb{N} and let G G be a simple graph with maximum degree Δ \Delta . A k k -colouring φ \varphi of G G is an assignment of colours from { 1 , 2 , … , k } \{1,2,\ldots,k\} to the vertices of G 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édi theorem states that a proper equitable k k -colouring exists whenever k ≥ Δ + 1 k\geq\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 ≥ 3 Δ 4 n\geq 3\Delta^{4} and k ≥ ( Δ + 2 ) / 2 k\geq(\Delta+2)/2 , then every n n -vertex graph with maximum degree at most Δ \Delta contains an equitable tree k k -colouring. This confirms a conjecture of Wu, Zhang, and Li when Δ \Delta is even and up to an additive constant of 1 1 otherwise for large n n . We also consider d d -degenerate colouring in which each colour class induces a d d -degenerate graph. Keywords : Equitable colouring; tree colouring; vertex arboricity; d d -degenerate graph 1 Introduction For integers p and q , let [p,q]=\{i\in\mathbb{Z}\colon p\leq i\leq q\} . In particular, we denote [1,q] by [q] . Let k\in\mathbb{N} and let G be a graph. A k -colouring \varphi:V(G)\rightarrow[k] is an assignment of colours to the vertices of G . The set of vertices assigned the same colour under \varphi is a colour class . An old conjecture of Erdős [ 5 ] states that any graph G has a proper equitable k -colouring if k\geq\Delta(G)+1 . Here, a proper equitable k -colouring of G is a k -colouring of G such that no two adjacent vertices receive the same colour and the sizes of any two distinct colour classes differ by at most one. This conjecture was proved by Hajnal and Szemerédi [ 8 ] , and a simpler proof was later provided by Kierstead and Kostochka [ 9 ] . The equitable chromatic number of a graph G , denoted by \chi_{=}(G) , is the smallest integer k such that G admits a proper equitable k -colouring. Note that a graph G which is equitably k -colourable may not be equitably k^{\prime} -colourable for some k^{\prime}>k . For example, \chi_{=}(K_{3,3})=2 , but K_{3,3} has no proper equitable 3 -colouring. The smallest integer k such that G has a proper equitable k^{\prime} -colouring for every number of colours k^{\prime}\geq k is called the equitable chromatic threshold of G , and is denoted by \chi_{\equiv}(G) . The following two conjectures regarding \chi_{=}(G) and \chi_{\equiv}(G) are still open. Conjecture 1.1 (Meyer [ 12 ] ) . For any connected graph G , \chi_{=}(G)\leq\Delta(G) , with the exception that G is a complete graph or an odd cycle. Conjecture 1.2 (Chen, Lih, and Wu [ 2 ] ) . For any connected graph G , \chi_{\equiv}(G)\leq\Delta(G) , with the exception that G is a complete graph, an odd cycle, or a complete bipartite graph K_{2m+1,2m+1} . A proper k -colouring of G can be viewed as a partition of V(G) into k independent sets. Lovász [ 11 ] considered the corresponding problem where each colour class induces a subgraph of maximum degree at most d . Whilst the equitable generalization was first investigated by Fan, Kierstead, Liu, Molla, Wu, and Zhang [ 7 ] , where each colour class induces a graph of maximum degree one. In this paper, we are interested in vertex colouring where each colour class induces a forest. A k -colouring of a graph G is a tree k -colouring if the subgraph of G induced on each colour class is a forest. The minimum such k is called the ( vertex ) arboricity of G , denoted by va(G) . This concept was proposed by Chartrand, Kronk, and Wall [ 1 ] , who proved that va(G)\leq\Delta(G)/2+1 for any graph G and va(G)\leq 3 for any planar graph G . Equitable tree colouring was first studied by Wu, Zhang, and Li [ 13 ] , who showed (among other results) that every planar graph with girth at least 5 has an equitable tree k -colouring for all k\geq 3 . They further conjectured that the girth condition can be removed but with constant k . This conjecture was confirmed by Esperet, Lemoine, and Maffray [ 6 ] with k=4 . For general graphs, Wu, Zhang, and Li [ 13 ] conjectured the following. Conjecture 1.3 (Wu, Zhang, and Li [ 13 ] ) . Let \Delta,k\in\mathbb{N} with k\geq(\Delta+1)/{2} . Then every graph with maximum degree at most \Delta has an equitable tree k -colouring. Conjecture 1.3 has been verified for several classes of graphs. It holds for graphs with \Delta(G)\geq|V(G)|/{2} by Zhang and Wu [ 16 ] , for d -degenerate graphs G with \Delta(G)\geq 9.818d by Zhang, Niu, Li, and Li [ 15 ] , for all 5-degenerate graphs by Chen, Gao, Shan, Wang, and Wu [ 3 ] , and for graphs G with \Delta(G)\leq 6 by Chen, Liu, and Zhang [ 4 ] . In this paper, we confirm Conjecture 1.3 for large graphs if \Delta(G) is even and up to an additive constant of 1 if \Delta(G) is odd. Theorem 1.4 . Let \Delta,k,n\in\mathbb{N} with k\geq(\Delta+2)/{2} and n\geq 3\Delta^{4} . Then every n -vertex graph with maximum degree at most \Delta has an equitable tree k -colouring. Furthermore, we consider the following generalization of tree colourings. A graph is called d - degenerate if every subgraph contains a vertex of degree at most d . For d\geq 0 , a d - degenerate k - colouring of a graph G is a k -colouring such that the subgraph induced on each colour class is d -degenerate. Note that a 0 -degenerate colouring is a proper colouring, and a 1-degenerate colouring is a tree colouring. Kim, Oum, and Zhang [ 10 ] showed that every planar graph has an equitable d -degenerate k -colouring for any d=2 , k=3 or d\geq 3 , k=2 . Zhang and Zhang [ 14 ] proposed the corresponding statement for tree colouring conjecture. Conjecture 1.5 (Zhang and Zhang [ 14 ] ) . Let \Delta,d,k\in\mathbb{Z} with d\geq 0 and k\geq(\Delta+1)/(d+1) . Then every graph with maximum degree at most \Delta has an equitable d -degenerate k -colouring. Note that the bound in Conjecture 1.5 is best possible by considering (disjoint union of) K_{\Delta+1} . Hajnal and Szemerédi [ 8 ] resolved the case when d=0 . Zhang and Zhang [ 14 ] confirmed the conjecture for (d+1) -degenerate graphs, graphs with bounded maximum average degree, and planar graphs with large maximum degree. We have the following result to support the conjecture. Theorem 1.6 . Let \Delta,d,k\in\mathbb{N} with k\geq\Delta/d+1 . Then every graph with maximum degree