The Chromatic Number of Finite Group Cayley Tables

Abstract

The chromatic number of a latin square $L$, denoted $\chi (L)$, is the minimum number of partial transversals needed to cover all of its cells. It has been conjectured that every latin square satisfies $\chi (L)\le |L|+2$. If true, this would resolve a longstanding conjecture---commonly attributed to Brualdi---that every latin square has a partial transversal of size $|L|-1$. Restricting our attention to Cayley tables of finite groups, we prove two main results. First, we resolve the chromatic number question for Cayley tables of finite Abelian groups: the Cayley table of an Abelian group $G$ has chromatic number $|G|$ or $|G|+2$, with the latter case occurring if and only if $G$ has nontrivial cyclic Sylow 2-subgroups. Second, we give an upper bound for the chromatic number of Cayley tables of arbitrary finite groups. For $|G|\ge 3$, this improves the best-known general upper bound from $2|G|$ to $\frac{3}{2}|G|$, while yielding an even stronger result in infinitely many cases.