Rectangle Free Coloring of Grids

Details Rectangle Free Coloring of Grids Rectangle Free Coloring of Grids

2010-05-20

arxiv.org/abs/1005.3750v1

Mathematics

Combinatorics

Scientific paper

A two-dimensional \emph{grid} is a set $\Gnm = [n]\times[m]$. A grid $\Gnm$ is \emph{$c$-colorable} if there is a function $\chi_{n,m}: \Gnm \to [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) (assuming a conjecture) \emph{exactly} which grids are 4-colorable. We use combinatorics, finite fields, and tournament graphs.

Affiliated with

Also associated with

No associations

Rating

Rectangle Free Coloring of Grids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rectangle Free Coloring of Grids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rectangle Free Coloring of Grids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-211336