Grid colorings in steganography.

IEEE Transactions on Information Theory 53 (2007), 1547-1549.

A proper vertex coloring of a graph is called rainbow if, for each vertex v, all neighbors of v receive distinct colors. A k-regular graph G is called rainbow (or domatically full) if it admits a rainbow (k+1)-coloring. The d-dimensional grid graph G_d is the graph whose vertices are the points of Z^d and two vertices are adjacent if and only if their l_1-distance is 1. We use a simple construction to prove that G_d is rainbow for all d >= 1. We discuss an important application of this result in steganography.