Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Engineering
On The Complexity Of Grid Coloring, Daniel Christopher Apon
On The Complexity Of Grid Coloring, Daniel Christopher Apon
Graduate Theses and Dissertations
This thesis studies problems at the intersection of Ramsey-theoretic mathematics, computational complexity, and communication complexity. The prototypical example of such a problem is Monochromatic-Rectangle-Free Grid Coloring. In an instance of Monochromatic-Rectangle-Free Grid Coloring, we are given a chessboard-like grid graph of dimensions n and m, where the vertices of the graph correspond to squares in the chessboard, and a number of allowed colors, c. The goal is to assign one of the allowed colors to each vertex of the grid graph so that no four vertices arranged in an axis-parallel rectangle are colored monochromatically. Our results include: 1. A conditional, …