The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs

Source abstract

The achromatic number of a graph $G$, denoted $χ_a (G)$, is the maximum number of colors in a proper vertex coloring of $G$. Generalizing a result of Maistrelli and Penman, we prove that for sufficiently large $q$, the achromatic number of the $k$-th power Paley graph is at least $\frac{q-1}{k} + 1$. This lower bound gives the correct order of magnitude in $q$, but determining the correct dependence on $k$ remains open for all $k \geq 3$. The achromatic number of Peisert graphs is shown to be $\frac{q+1}{2}$. These bounds are consequences of a general theorem involving Cayley graphs whose generating set is a union of cyclotomic classes. Using character sums and Weil's bound, we prove an upper bound that improves the standard trivial bound $\binom{ χ_a (G) }{2} \leq e(G)$. Finally, we consider random Cayley-sum graphs on an abelian group $Γ$ of order $n$, where elements are included in the generating set independently with probability $\frac{1}{2}$. We prove that the achromatic and pseudochromatic number of such a graph are both at most $\frac{(\sqrt{3}+o(1))n}{\sqrt{\log_2 n}}$ with high probability.