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

# On r-Equitable Colorings of Trees and Forests

## Alain Hertz et Bernard Ries

An r-equitable k-coloring c of a graph G=(V,E) is a partition of V into k stable sets $V_1(c),\cdots,V_k(c)$ such that $|\ |V_i(c)|-|V_j(c)|\ |\leq r$ for any $i,j\in \{1,\cdots,k\}$. 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 $r\geq 1$. Furthermore we explain how to extend our result to forests.

, 16 pages