EQUITABLE COLORING OF TREES

A graph is equitably k-colorable if its vertices can be partitioned in to 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 equita bly k-colorable if and only if (i) k greater-than-or-equal-to 2 when \ Absolute value of X - Absolute value of Y\ less-than-or-equal-to 1; (i i) k greater-than-or-equal-to max{3, inverted right perpendicular(Abso lute value of T + 1)/(alpha(T - N[upsilon]) + 2) inverted left perpend icular} when \Absolute value of X - Absolute value of Y] > 1. In case (ii), upsilon is an arbitrary vertex of maximum degree in T and the nu mber alpha(T-N[upsilon]) denotes the independence number of the subgra ph of T obtained by deleting upsilon and all its adjacent vertices. (C ) 1994 Academic Press, Inc.