G-2013-83
A Note on \(r\)-Equitable \(k\)-Colorings of Trees
and BibTeX reference
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
Research Axis
Publication
Jan 2014
and
YUJOR, 24(2), 293–298, 2014
BibTeX reference