It is conjectured that the mxn grid graph has a prime labeling for all positive integers m and n . It is known that for any prime p and any integer n such that 1≤n≤p 2 , there exists a prime labeling on the pxn grid graph P m x P n . Also, it is known that the ladder P 2 x P n has a prime labeling for all positive integers n . We assume that Goldbach's Even Conjecture and a strengthened variant of Lemoine's Conjecture are true in order to show that the 3xn grid graph P 3 x P n has a prime labeli