How can I demonstrate that I can colour a $2n\times\binom{2n}{2}$ chessboard, with $n$ different colours, such that there aren't $4$ separate unit squares of the same colour, the centers of which are vertices of a rectangle having sides parallel to the sides of the board?
[Math] Colouring a chessboard
coloringcombinatorics
Related Solutions
Assume without loss of generality that the two squares to be removed are in different rows. (Otherwise turn the board 90°).
First cover the board in horizontal dominoes, and connect the two squares by a zig-zag line like this:
which follows the rule that if the line goes through one end of a domino, it immediately connects to another end. (The requirement that the two squares have different colors ensure that this will be true of the end of the path if only we start out in the right direction for this to hold at the beginning). Now you can flip dominoes along the zig-zag line to produce a covering that avoids the two squares.
With a bit of (easy) special-casing for the same-row case, this strategy can be extended to any size board as long as one of the side lengths is even and the other is $\ge 2$.
For your first graph, the answer is dependent upon the color choices you make for vertex 1 and vertex 2. There are $k^2$ ways to color the two vertices, but if the vertices share the same color (there are $k$ ways to do this), then the remaining vertices can all be colored any of the remaining $k-1$ colors independently, so you have $k(k-1)^5$ ways to do this. If the two vertices have distinct colors (there are $k^2-k$ ways to do this), then the vertex adjacent to both vertices can be colored $k-2$ ways and the remainder can each be colored $k-1$ ways, for a total of $(k^2-k)(k-1)^4(k-2)$ ways. Thus we have a total of $$ k(k-1)^6 $$ distinct colorings.
But this formula should suggest a different argument: pick a vertex and color it ($k$ ways to do this) and then each subsequent vertex always has exactly $k-1$ choices for a color.
Best Answer
As usual, $[m]=\{1,2,\dots,m\}$ for each $m\in\Bbb Z^+$, and for any set $S$, $[S]^2$ is the set of unordered pairs of elements of $S$. For a positive integer $m$ and integers $a$ and $b$ define $a\oplus_m b$ to be the unique $k\in[m]$ such that $a+b\equiv k\pmod m$.
Now fix a positive integer $n$, and let $m=2n-1$. For $i,k\in\{0,\dots,m\}$ let $a_{i,k}=i\oplus_m k$, and let
$$b_{i,k}=\begin{cases} 0,&\text{if }i=k\\ a_{i,k},&\text{if }i\ne m\ne k\\ a_{i,i},&\text{if }i<k=m\\ a_{k,k},&\text{if }k<i=m \end{cases}$$
It’s not hard to check that $a_{i,m}=a_{i,1}$ and then that $\{b_{i,0},\dots,b_{i,m}\}=\{0,\dots,m\}$ for $i=0,\dots,m$. Moreover, it’s clear that $b_{i,k}=b_{k,i}$ for $i,k\in\{0,\dots,m\}$. For $c\in[m]$ let
$$P_c=\big\{\{i,k\}\in[m]^2:b_{i,k}=c\big\}\;,$$
and let $\mathscr{P}=\{P_c:c\in[m]\}$. Each $P_c\in\mathscr{P}$ is a partition of $[2n]$ into $n$ unordered pairs, and $\bigcup\mathscr{P}=[2n]^2$. For each $c\in[m]$ let $P_c=\big\{\{r_{c,k},s_{c,k}\}:k\in[n]\big\}$.
Index the columns of the board by $[m]\times[n]$, partition the cells of column $\langle c,q\rangle$ according to $P_c$, and for $k\in[n]$ color the cells in rows $r_{c,k}$ and $s_{c,k}$ with color $k\oplus_nq$.
Suppose that $r,s\in[n]$, $\langle c,q\rangle,\langle d,p\rangle\in[m]\times[n]$, $r\ne s$, and the cells at the intersections of these rows $r$ and $s$ with columns $\langle c,q\rangle$ and $\langle d,p\rangle$ are all the same color. Then $\{r,s\}\in P_c\cap P_d$, so $c=d$, $\{r,s\}=\{r_{c,k},s_{c,k}\}$ for some $k\in[n]$, $k\oplus_nq=k\oplus_np$, and $q=p$, so that $\langle c,q\rangle=\langle d,p\rangle$. Thus, no rectangle with sides parallel to the sides of the board has all four corners the same color.