Tyrone had a good solution to this problem:

Each time the table gets bigger, we add a new ring round the edge. In a (2N+1)x(2N+1) ring, we need N+1 colours.