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 Gd is the graph whose vertices are the points of Zopfd and two vertices are adjacent if and only if their l1-distance is 1. We use a simple construction to prove that Gd is rainbow for all d ges 1. We discuss an important application of this result in steganography