  Let $G$ be a graph and $t$ a nonnegative integer. Suppose $f$ is a mapping
from the vertex set of $G$ to $\{1,2,\dots, k\}$. If, for any vertex $u$ of
$G$, the number of neighbors $v$ of $u$ with $f(v)=f(u)$ is less than or equal
to $t$, then $f$ is called a $t$-relaxed $k$-coloring of $G$. And $G$ is said
to be $(k,t)$-colorable. The $t$-relaxed chromatic number of $G$, denote by
$\chi_t(G)$, is defined as the minimum integer $k$ such that $G$ is
$(k,t)$-colorable. A set $S$ of vertices in $G$ is $t$-sparse if $S$ induces a
graph with a maximum degree of at most $t$. Thus $G$ is $(k,t)$-colorable if
and only if the vertex set of $G$ can be partitioned into $k$ $t$-sparse sets.
It was proved by Belmonte, Lampis and Mitsou (2017) that the problem of
deciding if a complete multi-partite graph is $(k,t)$-colorable is NP-complete.
In this paper, we first give tight lower and up bounds for the $t$-relaxed
chromatic number of complete multi-partite graphs. And then we design an
algorithm to compute maximum $t$-sparse sets of complete multi-partite graphs
running in $O((t+1)^2)$ time. Applying this algorithm, we show that the greedy
algorithm for $\chi_t(G)$ is $2$-approximate and runs in $O(tn)$ time steps
(where $n$ is the vertex number of $G$). In particular, we prove that for $t\in
\{1,2,3,4,5,6\}$, the greedy algorithm produces an optimal $t$-relaxed coloring
of a complete multi-partite graph. While, for $t\ge 7$, examples are given to
illustrate that the greedy strategy does not always construct an optimal
$t$-relaxed coloring.
