Chromatic Number of Regular Walls

Abstract

We formalize the intuitive question of coloring the bricks of a wall in such a way that no repetition occurs in any row, nor any vertical line intersects two or more bricks with the same color. We achieve a complete classification up to the least number of required colors, among all dimensions of the walls, and all admitted incidences of the bricks. The involved combinatorial structures (namely, $regular$ $walls$) are a special case of more general structures, which can be interpreted as adjacency matrices of suitable directed hypergraphs. Coloring the bricks is equivalent to coloring the arcs of the corresponding hypergraph. Regular walls seem interesting also for their connections with latin rectangles.