The linzertorte problem, or a unified approach to painting, baking and weaving (Q1081611)

A d-dimensional grid graph is defined on d sets \(N_ i\), \(i=1,2,...,d\), \(N_ i=\{1,2,...,n_ i\}\) with vertex set \(N_ 1\times N_ 2\times...\times N_ d\) and the set of edges \(\{\) (x,y): for some i, \(| x_ i-y_ i| =1\) and \(x_ j=y_ j\) for all \(j\neq i\}\). A grid graph does not contain an odd cycle hence is 2-colourable. There is given lower bound of painting operations for vertex (line) colouring of d-dimensional grid graph. The present algorithm is optimal (achieves the lower bounds).