  A proper $k$-coloring of a graph $G$ is a \emph{neighbor-locating
$k$-coloring} if for each pair of vertices in the same color class, the two
sets of colors found in their respective neighborhoods are different. The
\textit{neighbor-locating chromatic number} $\chi_{NL}(G)$ is the minimum $k$
for which $G$ admits a neighbor-locating $k$-coloring. A proper
$k$-vertex-coloring of a graph $G$ is a \emph{locating $k$-coloring} if for
each pair of vertices $x$ and $y$ in the same color-class, there exists a color
class $S_i$ such that $d(x,S_i)\neq d(y,S_i)$. The locating chromatic number
$\chi_{L}(G)$ is the minimum $k$ for which $G$ admits a locating $k$-coloring.
Our main results concern the largest possible order of a sparse graph of given
neighbor-locating chromatic number. More precisely, we prove that if $G$ has
order $n$, neighbor-locating chromatic number $k$ and average degree at most
$2a$, where $2a\le k-1$ is a positive integer, then $n$ is upper-bounded by
$\mathcal{O}(a^2(k^{2a+1}))$. We also design a family of graphs of bounded
maximum degree whose order is close to reaching this upper bound. Our upper
bound generalizes two previous bounds from the literature, which were obtained
for graphs of bounded maximum degree and graphs of bounded cycle rank,
respectively. Also, we prove that determining whether $\chi_L(G)\le k$ and
$\chi_{NL}(G)\le k$ are NP-complete for sparse graphs: more precisely, for
graphs with average degree at most 7, maximum average degree at most 20 and
that are $4$-partite. We also study the possible relation between the ordinary
chromatic number, the locating chromatic number and the neighbor-locating
chromatic number of a graph.
