Grid Colorings in Steganography
Jessica Fridrich, Petr Lisoněk · IEEE Transactions on Information Theory · 2007
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${\BBZ}^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\ge 1$. We discuss an important application of this result in steganography.