The problem posed here is about colouring a 17x17 grid such that there is no monochromatic rectangle.
These problems have nothing in common aside from the word "colouring" and the number "4".
This problem differs in two ways.
First, we're not looking for all of the vertices to be different colors. We're looking for them to not all be the same color. This is easier to do.
Second, he's not trying to color a simple planar graph. He means every rectangle on the grid -- for example, a 7 x 8 rectangle in the middle somewhere. This is much, much harder to do.
(To be fair, I made the same mistake on a first reading of the problem.)
Otherwise the problem seemed trivial.
On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?
There's 289 points on the grid, and 4 options for each. So... 2^578 options.
Can this be brute forced?
That depends. Do you have a kilobit quantum computer available?
My bad - sorry.
I think that's quite a few. Your mileage may vary based on the force available to you for bruting.
You don't need quite that many -- you could test 2^289 (and you can probably skip many of them) and look for the "rectangle free subsets" that he mentions in the slides, and then just look for four of them that don't overlap. Still gonna take eons.
4^(17*17) ~= 10^173.. a bit too many to brute force, but I'm sure you could narrow the number down a lot with simple heuristics (though it would still be too large to brute force).
http://en.wikipedia.org/wiki/Dual_graph
In this case, the dual of a grid is a grid. So at least that part of it would be the same problem. The other distinctions are true, though.