Rectangle Free Coloring of Grids

MaRDI QIDQ6218820zbMATH OpenFDO

Authors S. Fenner, William Gasarch, Charles N. Glover, Semmy Purewal

Publication date 20 May 2010

Abstract: A two-dimensional emph{grid} is a set $Gnm=[n]imes[m]$. A grid $Gnm$ is emph{$c$-colorable} if there is a function $ch{i}_{n,m}:Gnmo[c]$ such that there are no rectangles with all four corners the same color. We address the following question: for which values of $n$ and $m$ is $Gnm$ $c$-colorable? This problem can be viewed as a bipartite Ramsey problem and is related to a the Gallai-Witt theorem (also called the multidimensioanl Van Der Waerden's Theorem). We determine (1) emph{exactly} which grids are 2-colorable, (2) emph{exactly} which grids are 3-colorable, and (3) emph{exactly} which grids are 4-colorable. We use combinatorics, finite fields, and tournament graphs.

This page was built for publication: Rectangle Free Coloring of Grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6218820)