# Maximum coloring of a graph with paths through uncolored vertices

Last night, I had a dream involving an intelligent spider which was only able to communicate by crawling around on a grid of words/phrases, like this one:

When I woke up, I wondered why some of the cells in the grid were empty. But it makes perfect sense! If the grid were full of words, like this one:

The spider would be unable to express statements such as "Hello! How's it going?" because it would crawl over other words while doing so.

This led me to the following question: for a $$w$$ by $$h$$ grid, what is the maximum number of words you can fit in the grid, such that there is a path between any two words which does not go through another word? (Let's assume the spider can't move diagonally)

Or in general, given a graph, what is the maximum number of vertices you can color, such that for any pair of two colored vertices, there is a path between them which only goes through uncolored vertices?

In the specific case of a 4x4 grid, the optimal layout is this:

And I think that this might be the optimal one for 9x9:

And for 10x10:

And for 11x11:

And I will conjecture that you can create the optimal coloring for an $$n$$x$$n$$ grid by just taking one of these patterns, depending on $$n \mod 3$$, and extending it (i.e. adding groups of three rows with one uncolored, and two colored, except for the last cell in the row). I have not however found a proof of this, and it is very possible that I'm wrong. But from this, we can get a lower bound on $$S(N)$$, the maximum number of colored cells for an $$N$$x$$N$$ grid:

It is possible that this should be $$=$$, not $$\geq$$, but I have not found a proof of this.

1. Is this already a well-known problem? (I couldn't find anything about it online)
2. Can you prove that the formula shown above is always optimal, or find a counter-example to it?
3. Can you extend this formula to any $$w$$x$$h$$ grid? (It shouldn't be too hard...)
4. Can you find a similar method/formula for the case where the spider can move diagonally?
5. I have written a program to solve this, but its running time is $$O(2^V E \log* (E))$$, so I have only been able to run it on a 5x5 grid in a reasonable amount of time. Can you find a better algorithm and/or prove that this problem is NP-hard/complete?

Edit: The above formula and diagram for 10x10 are wrong (well, not optimal). Here is a 10x10 grid with 59, instead of 57 words:

Perhaps adding 2 to the $$N \equiv 1 \mod 3$$ case does make it optimal...

Edit 2: The paper linked to by Peter Taylor was very helpful; bounds should actually help a lot with this problem, because once you have a lower bound $$L$$ and an upper bound $$U$$, you can, instead of searching all possible colorings, only search colorings with $$U < V < L$$, where $$V$$ is the number of colored vertices. In the case of 6x6, the bounds (22-24) that paper gives reduces the number of possibilities from $$2^{36} = 68719476736$$ to $${36 \choose 22} + {36 \choose 23} + {36 \choose 24} = 7358764500$$ -- a nearly 100-fold reduction. With this, I was able to confirm that the maximum for 6x6 is indeed 22, but their lower bound is actually slightly better than mine for numbers $$\geq 8$$. They also provide bounds for any rectangular grid, not just squares.

Also, here are the optimal configurations for squares where moving diagonally is allowed:

3x3

111
101
111


4x4

1111
1010
1101
1011


5x5

11111
10101
11011
10101
11111


6x6

111111
101101
110101
111011
100101
111111


It seems like the optimal thing for squares with odd side lengths is to create a border of 1s around a checkerboard pattern of 1s and 0s.

• OK. I think you can squeeze in 1 more word in the 10x10 by taking the leftmost column and moving it to the far right -- you can then extend the 3rd block from the top in that column from 2 to 3 words. – j_random_hacker May 12 '19 at 19:29
• If you imagine a vertex in the middle of each cell with 4 edges to its neighbours, then you can make any spanning tree in this graph, and then put words at all the leaves. This is because a spanning tree provides a path (exactly one in fact) between any two vertices, and none of these paths use a leaf except a path to or from that leaf. So an optimal solution will be a spanning tree with a maximum possible number of leaves. This problem is NP-hard in general graphs, but I don't know about the case of grid graphs. – j_random_hacker May 12 '19 at 19:33
• I think you could exactly solve slightly larger instances by using branch and bound. E.g. every word needs at least 1 non-word neighbour to be its "gateway", but a non-word cell can serve at most 4 word cells in this way, so you cannot have more than $\frac{4}{5}wh$ words in a $w \times h$ rectangle. So after building the first $i$ rows, if the number of words in them, plus $\frac{4}{5}w(h-i)$ is $\le$ than the number of words in the best $w \times h$ solution you have found so far, you know that the current partial solution cannot be extended to a better solution. – j_random_hacker May 12 '19 at 19:55
• Strikes me as the perfect question for Mathematics. They like this sort of puzzle, which has little to do with computer science. – Yuval Filmus May 13 '19 at 12:40
• cedric.cnam.fr/~bentzc/INITREC/Files/AP1.pdf has some bounds – Peter Taylor May 13 '19 at 13:31