Grid Colorings in Steganography

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 Zopf^d and two vertices are adjacent if and only if their l₁-distance is 1. We use a simple construction to prove that G_d is rainbow for all d ges 1. We discuss an important application of this result in steganography