  Recently, \citeauthor*{akbari2021locality}~(ICALP 2023) studied the locality
of graph problems in distributed, sequential, dynamic, and online settings from
a {unified} point of view. They designed a novel $O(\log n)$-locality
deterministic algorithm for proper 3-coloring bipartite graphs in the
$\mathsf{Online}$-$\mathsf{LOCAL}$ model. In this work, we establish the
optimality of the algorithm by showing a \textit{tight} deterministic
$\Omega(\log n)$ locality lower bound, which holds even on grids. To complement
this result, we have the following additional results:
  \begin{enumerate}
  \item We show a higher and {tight} $\Omega(\sqrt{n})$ lower bound for
3-coloring toroidal and cylindrical grids.
  \item Considering the generalization of $3$-coloring bipartite graphs to
$(k+1)$-coloring $k$-partite graphs, %where $k \geq 2$ is a constant,
  we show that the problem also has $O(\log n)$ locality when the input is a
$k$-partite graph that admits a \emph{locally inferable unique coloring}. This
special class of $k$-partite graphs covers several fundamental graph classes
such as $k$-trees and triangular grids. Moreover, for this special class of
graphs, we show a {tight} $\Omega(\log n)$ locality lower bound.
  \item For general $k$-partite graphs with $k \geq 3$, we prove that the
problem of $(2k-2)$-coloring $k$-partite graphs exhibits a locality of
$\Omega(n)$ in the $\onlineLOCAL$ model, matching the round complexity of the
same problem in the $\LOCAL$ model recently shown by
\citeauthor*{coiteux2023no}~(STOC 2024). Consequently, the problem of
$(k+1)$-coloring $k$-partite graphs admits a locality lower bound of
$\Omega(n)$ when $k\geq 3$, contrasting sharply with the $\Theta(\log n)$
locality for the case of $k=2$. \end{enumerate}
