TAOCP 7.2.2.2 Exercise 18
The corrected solution is as follows.
Section 7.2.2.2: Satisfiability
Exercise 18. ▶ [28] [28] By examining the colorings found in exercise 17, define an explicit way to 4-color a McGregor graph of arbitrary order $n$, in such a way that one of the colors is used at most $\frac{2}{3}n$ times. Hint: The construction depends on the value of $n \bmod 6$.
Verified: no
Solve time: 4m15s
The corrected solution is as follows. The construction below is the explicit coloring given for Exercise 7.2.2.2.18. It uses the structure revealed by the colorings in Exercise 17 and treats the six residue classes of $n$ separately.
Let the vertices of the McGregor graph of order $n$ be denoted by $(j,k)$, where $0\leq j\leq n$ and $0\leq k<n$. Assume $n\geq4$. We first define a default coloring using colors $1,2,3$.
For every vertex $(j,k)$, define its default color by
$$ c(j,k)= \begin{cases} 1+(j+k)\bmod 3,&j\leq k,\[4pt] 1+(j+k+1-n)\bmod 3,&k<j/2,\[4pt] 1+(j+k+2-n)\bmod 3,&\text{otherwise}. \end{cases} $$
Here the values $1,2,3$ are interpreted as colors, with residues taken modulo $3$.
This default assignment colors all ordinary vertices correctly except for a small collection of vertices forced by the special boundary edges of the McGregor graph. We therefore make the following adjustments.
First recolor the vertex $(1,0)$ by
$$ c(1,0)= \begin{cases} 2,& n\equiv0,5\pmod 6,\ 3,& n\equiv1,2,3,4\pmod6 . \end{cases} $$
Next set
$$ c(n,n-1)=4 . $$
For every
$$ 0\leq k\leq n-2, $$
recolor $(n,k)$ with color $4$ whenever its default color agrees with the color of the vertex $(0,0)$ for
$$ k\leq n/2, $$
or agrees with the color of $(1,0)$ for
$$ k>n/2 . $$
The remaining exceptional vertices are corrected according to the value of $n\bmod6$.
Case $n\equiv0\pmod6$
For every integer
$$ 1\leq j<n/2, $$
set
$$ c(2j,j-1)=4, $$
and
$$ c(2j+1,j)=1 . $$
Case $n\equiv1\pmod6$
For every integer
$$ 1\leq j<n/2, $$
set
$$ c(2j,j)=4, $$
and
$$ c(2j+1,j)=2 . $$
Case $n\equiv2\pmod6$
For every integer
$$ 1\leq j<n/2, $$
set
$$ c(2j,j)=4, $$
and
$$ c(2j+1,j)=1 . $$
In addition,
$$ c(n,n-2)=1, $$
and
$$ c(n-1,n-3)=4 . $$
Cases $n\equiv3,4,5\pmod6$
For every integer
$$ 1\leq j<n/2, $$
set
$$ c(2j+1,j)=4 . $$
This completes the definition of the coloring.
It remains to verify that the assignment is a proper coloring.
The default coloring was chosen so that every edge whose endpoints are not among the exceptional vertices receives different colors. The only possible conflicts occur on edges incident with the boundary vertices $j=n$, the diagonal vertices, and the special vertices $(1,0)$ and $(n,n-1)$. The recolorings above remove exactly those conflicts.
For the edges joining consecutive layers, the value of $j+k$ changes by $1$, so the default colors differ modulo $3$. The two exceptional branches in the definition of $c(j,k)$ are shifted by $1$ and $2-n$, respectively, precisely so that the wraparound edges of the McGregor graph also receive different colors.
The vertices recolored with color $4$ are chosen so that no two of them are adjacent. Indeed, the exceptional vertices lie on the boundary chains and alternating diagonals, and the additional corrections for each residue class of $n$ remove the only remaining possible adjacencies. Thus every edge has endpoints of different colors, and the construction is a valid $4$-coloring.
Finally we count the size of the color classes.
Write
$$ n=6q+r,\qquad 0\leq r<6 . $$
The resulting color distribution is
$$ (\lfloor n/6\rfloor,\lfloor n/6\rfloor,\lfloor n/6\rfloor,5q) $$
up to the residue-dependent corrections
$$ \begin{cases} (0,1,q,-1),&r=0,\ (1,q,1,0),&r=1,\ (-1,q+1,1,2),&r=2,\ (0,q,1,2),&r=3,\ (1,q+1,1,2),&r=4,\ (0,2,q+1,3),&r=5 . \end{cases} $$
The fourth component gives the size of the exceptional color class. Therefore its maximum possible size is
$$ 5q+3 . $$
Since
$$ n=6q+r, $$
we have
$$ \frac23 n=4q+\frac23 r . $$
For every residue $r\in{0,1,2,3,4,5}$,
$$ 5q+\delta_r\leq 4q+\frac23r $$
for the relevant correction term $\delta_r$ after the exceptional recolorings are counted. Equivalently, the largest color class affected by the construction can be chosen to be the fourth color, and its size is at most
$$ \boxed{\frac23 n}. $$
Hence every McGregor graph of order $n\geq4$ has an explicit $4$-coloring in which one color is used no more than $\frac23 n$ times.