Groupe d’études et de recherche en analyse des décisions

G-2011-40

On r-Equitable Colorings of Trees and Forests

et

An r-equitable k-coloring c of a graph G=(V,E) is a partition of V into k stable sets such that for any . In [B.-L. Chen and K.-W. Lih, Equitable Coloring of Trees, Journal of Combinatorial Theory, Series B 61, 83--87 (1994)], the authors gave a complete characterization of trees which are 1-equitably k-colorable. In this paper, we generalize this result and give a complete characterization of trees which are r-equitably k-colorable for any given . Furthermore we explain how to extend our result to forests.

, 16 pages