doiSerbia

A note on r-equitable k-colorings of trees

Hertz Alain (Ecole Polytechnique de Montréal and GERAD Montréal, Canada)
Ries Bernard (PSL, Université Paris-Dauphine, Paris Cedex, France)

A graph G = (V;E) is r-equitably k-colorable if there exists a partition of V into k independent sets V1, V2,... Vk such that ||Vi|- |Vj|| ≤ r for all i,j  {1,2... k}. In this note, we show that if two trees T1 and T2 of order at least two are r-equitably k-colorable for r ≥ 1 and k ≥ 3, then all trees obtained by adding an arbitrary edge between T1 and T2 are also r-equitably k-colorable.

Keywords: trees, equitable coloring, independent sets