Publication at Faculty of Mathematics and Physics |
2007
Abstract
(This paper is an extended abstract) We consider the d-dimensional grid with diagonals, which is the graph whose vertices are d-component vectors with components from {1,2,...,n} and edges connecting every two vertices that differ by at most 1 in every coordinate. We prove that whenever the vertices are colored by two colors, there exists a monochromatic connected subgraph with at leastt n^(d-1)-O(n^(d-2)) vertices, which is nearly tight.
We also consider a similar problem for triangulated grids.