Orthogonal colourings of Cayley graphs (Q2198400)

Let \(G=(V,E)\) be a graph, where \(V\) and \(E\) are the sets of vertices and edges, respectively. A (vertex) colouring of \(G\) is a labelling of the vertices with colours in such a way that no two vertices sharing the same edge have the same colour. Two colourings are said to be orthogonal if they satisfy the following condition: when two vertices have the same colour in one colouring, then they must have distinct colours in the other colouring. This notion of orthogonality for vertex colourings goes back to the work of \textit{Y. Caro} and \textit{R. Yuster} [Electron. J. Comb. 6, No. 1, Research paper R5, 14 p. (1999; Zbl 0909.05026)], though it appeared earlier in [\textit{D. Archdeacon} et al., Congr. Numerantium 47, 49--67 (1985; Zbl 0622.05023)] within the context of edge colourings. Furthermore, a \(k\)-orthogonal colouring of a graph \(G\) is a collection \(k\) orthogonal colourings that are mutually orthogonal. Accordingly, the \(k\)-orthogonal chromatic number \(O_{\chi_k}(G)\) is the minimum number of colours needed for a \(k\)-orthogonal colouring. In the paper under review, the authors investigate the notion of orthogonal colourings for several families of Caley graphs that often are all related to the group \(\mathbb{Z}_n\). Firstly, they consider \(\mathbb{Z}_n\) with generating set \(\{1,-1\}\) (the corresponding Cayley graph is nothing but the cycle graph \(C_n\)). In this case, the authors show that \(O_{\chi_2}(C_n)=\lceil\sqrt{n} \rceil\) if and only if \(n\) is strictly greater than 4. The proof is done by showing that the lower bound for \(O_{\chi_2}(C_n)\) is actually attained. The \(k\)-orthogonal chromatic number is also computed for other values of \(k\). Indeed, one may also vary the generating set. The authors determine the \(2\)-orthogonal chromatic number of \(\mathbb{Z}_{p^2}\), with \(p\) prime, for different generating sets provided that they are sufficiently small. Then, the Cayley graphs of \(\mathbb F_{p^k}\), \(p\) prime, are also investigated. Finally, colourings of Cartesian products of graphs are studied. A particular case of interest, which is analysed in the present paper, are the so-called Hamming graphs \(H(p,d)\). These are the Cayley graphs of \(\mathbb{Z}_p^d\).