When chessboards meet dominoes

You probably have heard about the following brainteaser :

Consider a $8\times 8$ chessboard. Remove two extreme squares (top-left and bottom-right e.g.). Can you fill the remaining chessboard with $1\times 2$ dominoes ?

The answer lies in a coloring argument. The problem, however, does not use the fact that the chessboard is colored. I would like to know improved examples of coloring problems like this one.

For instance, could you extend the problem with Tetris-like L-shaped dominoes and solve it using more than two colors ?

Solomon Golomb's book Polyominoes presents a number of arguments of this type.

One that I remember is: a square is deleted from an 8×8 checkerboard. Can the remaining 63 squares be covered by 21 1×3 rectangles? The answer involves coloring the checkerboard in three colors in alternating diagonal stripes:

This colors the 64 squares of the checkerboard with 21 green squares, 21 yellow squares, and 22 blue squares. Each 1×3 rectangle must cover exactly one square of each color. The deleted square therefore cannot be any of the green or yellow ones, nor any of the squares equivalent to one of these under a rotation or reflection of the checkerboard:

(This is four copies of the first diagram, superimposed, with suitable rotations.)

This eliminates all but 4 squares from consideration, namely the four bright blue ones in the previous diagram. So the only solutions involve deleting one of these four blue squares.

There are a number of analogous arguments about polyhexes that depend on a three-coloring of a hexagonal lattice:

For example, there are three different trihexes, which are made by joining three hexagons; two of these are guaranteed to cover exactly one cell of each color, no matter how they are placed.

I once wasted a lot of time trying to make myself a set of tetrominoes by marking up a 4x5 rectangle and cutting it apart, and I felt rather foolish when I realized that a straightforward checkerboard coloring shows that this is impossible. There are 5 tetrominoes, and four of them must cover two black and two white squares each. The 5th is T-shaped, and must cover three black squares and one white (or vice versa).

So they cannot possibly tile a 4×5 rectangle, which has equal numbers of black and white squares.

A woodworm is sitting at the centre of a cube that's divided into $3^3$ identical cubelets. The woodworm can go from the centre of one cubelet to the centre of another in any edge-parallel direction. The woodworm would like to eat its way through the cube such that it visits the centre of each cubelet exactly once. Is this possible?

I searched for math.SE questions and answers that involve colouring of tilings and the like; here are two interesting ones that I found:

The Mathematics of Tetris

A tiling puzzle/question