Efficient computation of the modular chromatic numbers of trees (Q2839730)

A modular \(k\)-coloring, \(k \geq 2\), of a graph \(G\) without isolated vertices is a coloring of the vertices of \(G\) with the elements in \(\mathbb{Z} k\) (where adjacent vertices may be colored the same) having the property that for every two adjacent vertices of \(G\), the sums of the colors of their neighbors are different in \(\mathbb{Z} k\). The minimum \(k\) for which \(G\) has a modular \(k\)-coloring is the modular chromatic number \(mc(G)\) of \(G\). The modular chromatic number of a graph is at least as large as its chromatic number. NEWLINENEWLINENEWLINE NEWLINE\textit{F. Okamoto, E. Salehi} and \textit{P. Zhang} [Bull. Inst. Comb. Appl. 58, 29--47 (2010; Zbl 1200.05087)] proved that \(3\geq mc (T) \geq 2\) for every nontrivial tree \(T\). Here the authors present an efficient algorithm that computes the modular chromatic number of a given tree.