Efficient Computation of the Modular Chromatic Numbers of Trees

Abstract

A modular $k$-coloring, $k\ge 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 in $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$. It is known that $2\le \text{mc}(T)\le 3$ for every nontrivial tree $T$. We present an efficient algorithm that computes the modular chromatic number of a given tree.