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


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


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