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 ${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 $dge 1$. We discuss an important application of this result in steganography.