%0 Generic %1 goddyn2018chromatic %A Goddyn, Luis %A Halasz, Kevin %A Mahmoodian, E. S. %D 2018 %K 4330 colouring graph %T The Chromatic Number of Finite Group Cayley Tables %U http://arxiv.org/abs/1805.06979 %X 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) |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|3$, this improves the best-known general upper bound from $2|G|$ to $32|G|$, while yielding an even stronger result in infinitely many cases.

@misc{goddyn2018chromatic, 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) \leq |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|\geq 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.}, added-at = {2021-09-06T18:18:16.000+0200}, author = {Goddyn, Luis and Halasz, Kevin and Mahmoodian, E. S.}, biburl = {https://www.bibsonomy.org/bibtex/2f08ec15ece30f90190b44fa7b16b73c9/j.c.m.janssen}, description = {The Chromatic Number of Finite Group Cayley Tables}, interhash = {14b44236d88261703af0ba0c722383fa}, intrahash = {f08ec15ece30f90190b44fa7b16b73c9}, keywords = {4330 colouring graph}, note = {cite arxiv:1805.06979}, timestamp = {2021-09-06T18:26:50.000+0200}, title = {The Chromatic Number of Finite Group Cayley Tables}, url = {http://arxiv.org/abs/1805.06979}, year = 2018 }