Consider ways of coloring the $n \times n$ grid with $r$ labels so that no two labels are adjacent (horizontally or vertically) in more than one place.
Is there a good upper or lower bound on the minimum integer $r_n$ such that the $n \times n$ grid has an $r_n$-coloring?
Non-example
The following grid would not be a valid $7$-coloring because (AX, AY) and (CY, BY) are both (1, 2) adjacencies:
A [1, 2, 7]
B [3, 2, 6]
C [4, 1, 5]
X Y Z
Examples
For example, on the $4 \times 4$ grid, the following $7$-coloring will work, but there are no $6$-colorings
[1, 1, 2, 2]
[3, 4, 4, 5]
[2, 6, 7, 1]
[7, 3, 5, 6]
Similarly, on the $5 \times 5$ grid, the following $9$-coloring will work, but there do not exist any $8$-colorings.
[1, 1, 2, 2, 3]
[3, 4, 4, 5, 3]
[6, 6, 7, 1, 8]
[9, 2, 7, 9, 8]
[4, 8, 5, 5, 6]
An example of an $8$-coloring on a $4 \times 5$ grid shows that there may be some structure to the coloring:
[1, 1, 2, 2, 3]
[3, 4, 4, 5, 3]
[6, 6, 7, 5, 8]
[2, 8, 7, 1, 8]
Conjecture
Empirical data for the first nine terms shows that $r_n = 2n - 1$ for $n \leq 6$. and $r_n \leq 2n - 1$ for $n \leq 9$. A stupid (?) conjecture is that $r_n = 2n - 1$.
I don't know about an upper bound, i.e., a construction of a coloring, but I think one can show fairly easily that $2n-1$ is a lower bound, which makes the conjecture reasonable. Assume $n > 1$, to avoid triviality. The main observation is that if the color $t$ occurs on two different squares $S_1$ and $S_2$, then if $C_1$ and $C_2$ denote the colors on squares adjacent to $S_1$ and $S_2$ respectively, the sets $C_1$ and $C_2$ must be disjoint, except that possibly one pair of squares can have $t \in C_i \cap C_j$ (if the squares are adjacent and see each other).
Suppose we have some valid coloring with $r$ colors. For each color $t$, let $i_t$, $e_t$, and $c_t$ denote the number of occurrences of $t$ on the interior, edge, and corner squares of the grid, respectively. The observation above gives $4i_t + 3e_t + 2c_t \leq r+1$, since the color-sets arising from these squares are disjoint subsets of $\{1, \ldots, r\}$, except for the possible double-count of $t$ occuring once. Summing over all $t$ gives $4(n-2)^2 + 12(n-2) + 8 \leq r(r+1)$, since $\sum_t i_t$ is just the number of interior squares, and likewise for the other quantities. This simplifies to $4n(n-1) \leq r(r+1)$.
Now for positive integers $n$ and $r$, the inequality $4n(n-1) \leq r(r+1)$ is equivalent to $r \geq \frac{1}{2}\left(\sqrt{16n^2 - 16n + 1} - 1\right)$. Finally, whenever $n > 1$, we have $\frac{1}{2}\left(\sqrt{16n^2 - 16n + 1} - 1\right) > 2n-2$, so that $r > 2n-2$. As $r$ and $n$ are integers, this implies $r \geq 2n-1$.
Note, also, that the last step here cannot be pushed further to find, say, an $n$ forcing $r \geq 2n$. If such an $n$ exists, a different proof would be needed to show that $2r-1$ colors don't suffice.