Equitable coloring of trees (Q1328387)

A graph \(G\) is said to be equitably \(k\)-colourable if the vertices of \(G\) can be partitioned into \(k\) independent sets \(V_ i\) such that \(\| V_ i | - | V_ j \| \leq 1\) for all \(i\) and \(j\). We regard a non-null tree \(T\) as a bipartite graph \(T(X,Y)\). The authors show that \(T\) is equitably \(k\)-colourable if and only if \[ k \geq 2 \quad \text{for} \quad \| X | - | Y \| \leq 1 \quad \text{and} \tag{i} \] \[ k \geq \max \Bigl \{3, \biggl \lceil \bigl( | T | + 1 \bigr) \bigl/ \biggl( \alpha \bigl(T - N(v) \bigr) + 2 \biggr) \biggr \rceil \Bigr\} \quad \text{for} \quad \| X | - | Y \|>1, \tag{ii} \] where \(v\) is an arbitrary vertex of maximum degree in \(T\) and \(\alpha(T-N(v))\) denotes the independence number of the subgraph of \(T\) obtained by deleting \(v\) and all its adjacent vertices.