### G-2013-83

# A Note on \(r\)-Equitable \(k\)-Colorings of Trees

## Alain Hertz and 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.

Published **November 2013**
,
8 pages