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

# A Note on $$r$$-Equitable $$k$$-Colorings of Trees

## Alain Hertz et Bernard Ries

A graph $$G = (V,E)$$ is $$r$$-equitably $$k$$-colorable if there exists a partition of $$V$$ into $$k$$ independent sets $$V_1, V_2, \ldots, V_k$$ such that $$||V_i| - |V_j|| \leq r$$ for all $$i, j\in \{1, 2, \ldots, k\}$$. In this note, we show that if two trees $$T_1$$ and $$T_2$$ of order at least two are $$r$$-equitably $$k$$-colorable for $$r \geq 1$$ and $$k \geq 3$$, then all trees obtained by adding an arbitrary edge between $$T_1$$ and $$T_2$$ are also $$r$$-equitably $$k$$-colorable.

, 8 pages