COLOURING GAMES BASED ON AUTOTOPISMS OF LATIN HYPER-RECTANGLES

摘要

Every partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the Theta-stabilized (a, b)-colouring game for Hamming graphs, a variant of the (a, b)-colouring game so that each move must respect a given autotopism Theta of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case.