On covering an independent set in a grid with a second independent set
Rachel Rue · Journal of Graph Theory · 1996
We show that for every independent set O in an n × m grid, n, m > 1, there is a second independent set X with the property that every member of O is adjacent to at least one member of X. The proof gives a construction for X. Equivalently, we show that for every maximal independent set in a grid, there is a second, disjoint, maximal independent set. © 1996 John Wiley & Sons, Inc.