A Note on R-Equitable K-Colorings of Trees


Alain Hertz, 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,...,V_k$ such that $| |Vi| - |V_j| | \leq r$ for all $i, j \in \{1, 2, ..., 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.