Given a polyomino $P$ define as $f(P)$ the number of ways to color its edges red black and white so that each square has two edges of one color and two of another. Lemma $1$: If $P$ is a polyomino obtained by gluing a new square onto a polyomino $Q$ such that the new square shares two edges with $P$ then $f(P)=2f(Q)$. Proof: Every coloring of $P$ can be obtained by first coloring $Q$ and then coloring the two exclusive edges of the new square, this can be done in two ways. If the two old edges have the same color then we get to choose the color for the new edges, and if the two old edges have different colors then we get to choose which of the new edges gets which color. Lemma $2$: If $P$ is a polyomino obtained by gluing a new square onto a polyomino $Q$ such that the new square shares one edge with $P$ then $f(P)=6f(Q)$. Proof: Every coloring of $P$ can be obtained by first coloring $Q$ and then coloring the three exclusive edges of the new square, this can be done in three ways. First select the edge which is going to have the same color as the old edge in $3$ ways and then select the color for the other two edges. Notice that the number of ways to color an isolated square is $36$. From here we can build the $m\times n$ rectangle by gluing new squares by filling out the rows one by one from left to right. When filling the first row we glue $m-1$ squares which only share $1$ side each time. So the number of ways to color the $m\times 1$ rectangle is $6^{m+1}$. And after this, every time we fill a new row we multiply by $6$ once and by $2$ $m-1$ times. Therefore the number of ways to colore the $n\times m$ rectangle is $3^{n+m}\times 2^{nm+1}$

Gamamal wrote: Given a polyomino $P$ define as $f(P)$ the number of ways to color its edges red black and white so that each square has two edges of one color and two of another. Lemma $1$: If $P$ is a polyomino obtained by gluing a new square onto a polyomino $Q$ such that the new square shares two edges with $P$ then $f(P)=2f(Q)$. Proof: Every coloring of $P$ can be obtained by first coloring $Q$ and then coloring the two exclusive edges of the new square, this can be done in two ways. If the two old edges have the same color then we get to choose the color for the new edges, and if the two old edges have different colors then we get to choose which of the new edges gets which color. Lemma $2$: If $P$ is a polyomino obtained by gluing a new square onto a polyomino $Q$ such that the new square shares one edge with $P$ then $f(P)=6f(Q)$. Proof: Every coloring of $P$ can be obtained by first coloring $Q$ and then coloring the three exclusive edges of the new square, this can be done in three ways. First select the edge which is going to have the same color as the old edge in $3$ ways and then select the color for the other two edges. Notice that the number of ways to color an isolated square is $36$. From here we can build the $m\times n$ rectangle by gluing new squares by filling out the rows one by one from left to right. When filling the first row we glue $m-1$ squares which only share $1$ side each time. So the number of ways to color the $m\times 1$ rectangle is $6^{m+1}$. And after this, every time we fill a new row we multiply by $6$ once and by $2$ $m-1$ times. Therefore the number of ways to colore the $n\times m$ rectangle is $3^{n+m}\times 2^{nm+1}$ Wrong solution. An isolated square can be colored in $18$ ways. You can choose $2$ colors from $3$ colors in three ways and you color the edges of the square according to condition in $6$ ways. $3$ time $6$ is $18$. Due to this answer must be $2^{mn} \cdot 3^{m+n}$