Chromatic number of a graph on a chess board

Question

For a chess piece Q, the Q-graph is the graph whose vertices are the squares of the chess board and the two squares are adjacent if Q can move from one of them to the other in one move. Find the chromatic number of the Q-graph when Q is (a) the king, (b) a rook, (c) a bishop, (d) a knight.

So my first thought would be to think of each distinct move a piece could make if it was in the center of the board since this would be the maximal degree of all vertices on the graph and therefore the most neighbors a graph could have showing how many distinct colors are needed?

Answer 1

Within a $2\times 2$ square, the king can move from any directly to eevery other field, hence we need at least four colours. If we assign colour $(x\bmod 2, y\bmod 2)$ to field $(x,y)$, ew see that $4$ colours also suffice.

For the rook, all fields in one column are mutually adajacent and hence must have different colours, thus requiring at least $8$ colours. But eight colours also suffice if you assign $x+y\bmod 8$ to $(x,y)$.

Similarly, the bishop has adjacent fields along a diagonal, thus also requiring eight colours. But eight colours also suffice by assigning colour $x$ to $(x,y)$.

For the knight, the original checssboard colouring witnesses that the chromatic numbre is 42$.

Answer 2

(a) The king connects $4$ squares, so the chromatic number is at least $4$. If we colour the squares according to the parity of the rank and the parity of the file, the king can’t keep both parities the same; so the chromatic number is $4$.

(b) A rook connects all $8$ squares in a rank or file, so the chromatic number is at least $8$. If each square is coloured by the residue of the sum of the rank and file modulo $8$, the rook can’t stay on the same residue; so the chromatic number is $8$.

(c) A bishop on the long diagonal connects $8$ squares, so again the chromatic number is at least $8$. The bishop can’t stay on the same rank or file, so we can colour the squares according to their rank or file; so the chromatic number is again $8$.

(d) has already been solved in the comments: You can colour each square with the colour it has on the chessboard, so the chromatic number is $2$.