Equitable Coloring of Trees

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets of as near equal sizes as possible. Regarding a non-null tree T as a bipartite graph T(X, Y), we show that T is equitably k-colorable if and only if (i) k ≥ 2 when | |X| − |Y| | ≤ 1; (ii) k ≥ max{3, ⌈(|T| + 1)/(α(T − N[v]) + 2)⌉} when | |X| − |Y| | > 1. In case (ii), v is an arbitrary vertex of maximum degree in T and the number α(T − N[v]) denotes the independence number of the subgraph of T obtained by deleting v and all its adjacent vertices.