Elena Konstantinova: Chromatic properties of Cayley graphs

In this talk recent results on chromatic properties of Cayley graphs and random Cayley graphs will be presented. In 2013 Noga Alon published the first pioneer work on the chromatic number of random Cayley graphs [N. Alon, The chromatic number of random Cayley graphs, European Journal of Combinatorics, 34 (2013) 1232-1234.] He considered the typical behavior of the chromatic number of a random Cayley graph of a given group of order n with respect to a randomly chosen set. This behavior depends on the group. General, cyclic and abelian groups were considered by Noga Alon. As open problems, he suggested consider more accurately the case of the symmetric group. In this talk we present some results on Cayley graphs on the symmetric group. In particular, it is shown that a random Cayley graph on the symmetric group is not, asymptotically almost surely, bichromatic for any large n. The chromatic properties of the Pancake graphs P_n will be also considered. It is shown that for any n > 2 the total chromatic number of P_n is n, and the chromatic index of P_n is n − 1. Upper bounds on the chromatic number of P_n are also given.