Edit: Guess I hurried a little bit, thanks to math_explorer for pointing out my error.

AlexanderMusatov wrote: To prove that every such $(m,n)$ work, consider $2 \times 2$ and $3\times 2$ cycles. A $3 \times 2$ region with one color does not result in a $3 \times 2$-cycle... the middle squares have $3$ neighbors, which is not even. I think the answer is that $m, n$ are both even, which is easily proved possible with $2 \times 2$ blocks of different colors. To prove this is necessary, argue by contradiction. Suppose a dimension, WLOG the width of the grid, is odd. For simplicity, we surround the whole grid with a border of thickness 1, colored entirely with an additional, different color; clearly the problem condition is preserved, and the width is still odd. Consider any horizontal block $A$ of one color $c$ with an odd width and no squares of the same color neighboring it to its top, left, or right: ......... .ccccccccc. <- odd -> At least one exists, namely the top edge of our modified grid, consisting entirely of the new color we added. So we can consider the shortest of all these blocks $A$. Obviously it's a contradiction if the block's length is 1, because the lone square in our block could have at most one same-color neighbor. So the block's length is at least 3. To satisfy the problem condition, the leftmost and rightmost squares in this block each need a square of color $c$ below it, but none of the other squares can. So the block of squares B directly below $A$ consists of an odd block of squares, none of which are colored $c$, flanked with two squares with $c$: ......... .ccccccccc. cxxxxxxxc If we cut $B$ without the leftmost and rightmost squares into contiguous blocks of the same color, we must have at least one block with odd width, because the total width is odd. Then that block, flanked with different colors to its left and right and with all squares above it colored $c$, is also one of the configurations we were considering, and even shorter, a contradiction. So a grid with one odd dimension cannot be colored to satisfy the problem condition.

Here's my approach: Instead of using colors and unit squares, consider some chains and a system of lattice points. We can reformulate the condition "there exists a set $C=\{c_1,\ldots,c_k\}$ ($k\ge1$) of colors and an assignment of colors to each of the $mn$ unit squares of a $m\times n$ grid such that for every color $c_i\in C$ and unit square $S$ of color $c_i$, exactly two direct (non-diagonal) neighbors of $S$ have color $c_i$" as the following: We can partition the points of a $m\times n$ in chains of length at least 4 (with the exception of the ones which are formed of the unit squares of a $2\times n$, $n\in \mathbb{Z}$, $n\ge 3$). A chain is a set of lattice points $\{s_1,\;s_2,\;s_3,\dots,\;s_k\mid k\in\mathbb{Z},\;k\ge 4\} $ such that $s_i$ and $s_{i+1}$ are neighbors, $i=\overline{1,k}$ and $s_{k+1}=s_1$. We call $k$ the length of the chain. We claim that $m,\;n$ are even is necessary and enough for the unit squares to be able to be partitioned in chains. Define the area of a chain as the area of the polygon formed by connecting any two adjacent points. We first prove the following lemma: Lemma. The intersection between any chain and column is a set of unit squares with even cardinality. To prove this lemma, it suffices that the length of any side of a chain is of even cardinality. We shall prove this using induction. Consider the following statements: $p_n$: "The sides of a chain (which is a part of a partition of the grid in chains) of area $n$, have even cardinality.". We claim that $p_n$ is true $\forall n\in\mathbb{N^{*}}$. For $n=1$, it is obvious because the only existing chain of area $1$ is the one formed by the vertices of a unit square. Moving on, supposing that $p_i$ is true, $\forall i\le n$, we shall prove that $p_{n+1}$ is also true. Consider a chain of area $n+1$. The "interior" of the chain is formed of other chains, thus the length of any side of the main chain can be rewritten as the sum (sometimes the difference) of the lengths of the sides of other chains $+2$ (because all sides contain exactly two vertices of the chain) as shown in the example below. $1111111111111111$ $1222233333344441$ $1255236666347741$ In this example, the upper side of the chain (denoted by $1$s) has other sides of other chains ($2$, $3$, and $4$) "glued" to it. As mentioned in the inductive step, all the sides of the chains inside the main chain have even cardinality. Simply remove a whole chain (with its interior) and create a new chain (in some special cases, the side of a chain inside the main chain is longer than the side of the main chain, but there is no risk whatsoever!). Obviously, this new chain and the chains inside the main chain have an area less than $n$ and so the inductive step is proved. Back to our lemma, it should be easy using the above result. Let $c$ and $C$ be a random column and a random chain. Furthermore, consider an ant on the chain and a fixed orientation. The ant will also walk with the same orientation. The ant can pass through $c$ in the following ways: (i) Passes $c$ from the left to right and then comes back from right to left (of course, it can also be from right to left and then from left to right) as shown in the figure below ($0$ means anything, $1$ is the chain, $2$ is the column, and $3$ is where they intersect). This creates two intersections. $00000010000$ $00022232220$ $00000010020$ $00000010020$ $00222232220$ $00000010000$ (ii) The ant walks on $c$ as shown in the figure below. Using the previous result, this creates an even number of intersections. $00000010000$ $02222230000$ $00000030000$ $00000030000$ $02222230000$ $00000010000$ Hence the lemma is proved. Using the lemma, it is obvious that $m$ must be even. In a similar way, we can prove that $n$ is even. An example for a pair of even numbers $(n,m)$ would be to partition the points in chains of area $1$ (the ones that are formed of the vertices of unit squares).

Hmm, can't we just induction on $n\in \mathbb{Z}^+$ that the "connected" shape $S$ form by joining cells together with area $n$ can be completely tiled with pairwise disjoint cycles of cells if and only if all sides of $S$ have even length?

The answer is $m \equiv n \equiv 0 \pmod 2$ which is done by coloring $2 \times 2$ blocks by colors. For the reverse direction, we say that a bracket is a shape of the following form, where $c$ is a color: \[ \begin{bmatrix} c & c \\ c & \ast \\ c & \ast \\ \vdots & \vdots \\ c & \ast \\ c & \ast \\ c & c \end{bmatrix} \]Note that in a bracket, none of the starred cells which are ``clamped'' by it can have color $c$. Claim: All brackets have even height. Proof. It's enough to prove the statement ``if a bracket has height $n$ then $n$ is even'' by strong induction. If $n=1$ or $n=2$ it is clear. For the inductive step, we see the starred cells should be the left edges of more brackets (exercise). These brackets have height summing to $n-2$; they all have even size and hence so does $n$. $\blacksquare$ To finish, note that the left edge of the $m \times n$ board is also the left edges of some brackets, hence $m$ is even. Similarly $n$ is even, and done.

My solution:The key ingredient is the following claim: Claim:If such a coloring is possible then there exist a coloring such that the board is divided into some $2\times 2$ monochromatic squares with no two neighbor $2*2$ squares having the same color. Proof:If all the cycles of a color are squares then we are done otherwise we have a non-square cycle and so it has some area inside in it filled with other cycles if there only square cycles in it hold there otherwise continue until you get a non-square cycle that contains only square-cycles inside it.It is easy to see we can delete this cycle and the squares inside it and replace all with new squares.Continue this until we have no non-square cycles(The Process indeed terminates since the number of squares is increasing)and so the claim is true. Now we have to solve the following problem: Problem wrote: Determine all pairs of natural numbers $(m,n)$ so that the $m \times n$ square can be tiled with $2 \times 2$ squares. And this is obvious $m,n$ should be even and a tiling is possible for that kind of boards.

Quote: It is easy to see we can delete this cycle and the squares inside it and replace all with new squares Wrong. Consider the $2\times 2$ squares ${1,2}\times {1,2}$ and ${2,3}\times {3,4}$ and the closed curve enveloping them. These three paths have a total area of $26$.

I believe this works. There's no real ``trick" to this solution, just lots of characterization. The answer is all $(m, n)$ that are both even. For construction, make lots of $2 \times 2$ squares. To see that these are the only possible grids, we employ the following argument. Define a closed region to be the set of all squares with color $c_i$ for some $i$ and the set of all squares that are enclosed by them. Claim. [Housekeeping] The only closed region that encloses no squares is the $2 \times 2$ square. Proof. Suppose there exists another such region. Let $C_1$ be any convex corner of the region and $C_2$ and $C_3$ the squares that border $C_1$. Then for $C_4$ the square such that $C_1C_2C_3C_4$ is a $2 \times 2$ square, $C_4$ is located within the interior of the closed region. It follows that $C_2$ and $C_3$ may not border any more squares, from where connectivity implies the region is precisely a $2 \times 2$ square. $\blacksquare$ Claim. [Key Claim] Every closed region has even dimensions, i.e. even width at any length index and even length index at any width index. Proof. For simplicity we will call these closed regions even regions. Notice that if a region is a union of two even regions, then it must itself be an even region. Now we proceed by induction on the number of squares in the closed region. For the base case, the smallest possible closed region is a $2 \times 2$ square, which is indeed an even region. For the inductive step, take any closed region and remove all the squares colored $c_i$. These squares form a ``band" around the periphery of the region, so the parity of the width or length measured at any given index will remain the same. The region that remains is a union of some (at least one) closed regions. By the inductive hypothesis, each of these closed regions is even, so their union is even, and the original closed region is also even, as required. $\blacksquare$ But our original $m \times n$ grid is a union of closed regions, so it must have even dimensions too.

There exists such a coloring if $m$ and $n$ are both even – just partition the board into $2 \times 2$ squares. If $m$ (the width) is odd, we have a contradiction from looking at the top edge: in particular, we can find progressively shorter horizontal runs of odd length, until we get a run of length $1$. This is a contradiction. [asy][asy] unitsize(0.5cm); int width = 17; int height = 5; fill((0,height)--(2,height)--(2,height-2)--(0,height-2)--cycle, mediumgray); fill((2,height)--(13,height)--(13,height-2)--(12,height-2)--(12,height-1)--(3,height-1)--(3,height-2)--(2,height-2)--cycle, lightred); fill((13,height)--(17,height)--(17,height-2)--(16,height-2)--(16,height-1)--(14,height-1)--(14,height-2)--(13,height-2)--cycle, mediumgray); fill((3,height-1)--(8,height-1)--(8,height-3)--(7,height-3)--(7,height-2)--(4,height-2)--(4,height-3)--(3,height-3)--cycle, lightgreen); fill((8,height-1)--(12,height-1)--(12,height-3)--(11,height-3)--(11,height-2)--(9,height-2)--(9,height-3)--(8,height-3)--cycle, mediumgray); fill((4,height-2)--(7, height-2)--(7,height-4)--(6, height-4)--(6,height-3)--(5,height-3)--(5,height-4)--(4,height-4)--cycle, lightred); fill((5,height-3)--(6,height-3)--(6,height-4)--(5,height-4)--cycle, lightgreen); for(int i = 1; i < width; ++i ) { draw((i,0)--(i,height), black); } for(int i = 1; i < height; ++i ) { draw((width,i)--(0,i), black); } draw((0,0)--(0,height)--(width,height)--(width,0), black+linewidth(2)); fill((-0.5,-0.5)--(width+0.5,-0.5)--(width+0.5,0.5)--(-0.5,0.5)--cycle, white); [/asy][/asy] Similarly, $n$ must be even.