Redicoloring some classes of circulant tournaments

Abstract

Given a digraph $D$ with no loops, the \textit{dicoloring graph} of $D$, denoted by ${\mathcal{D}}_k(D)$, is the graph whose vertices are the acyclic $k$-colorings of $D$ and two colorings are adjacent in ${\mathcal{D}}_k(D)$ if they differ in color on exactly one vertex. In this paper, we prove that there is no expression $\varphi (\vec{\chi })$ in terms of the dichromatic number $\vec{\chi }$, such that the graph ${\mathcal{D}}_k(D)$ is connected for all graphs $D$ and integers $k\ge \varphi (\vec{\chi })$. We give conditions for the dicoloring graph of two infinite families of circulant tournaments to be connected, and we provide upper bounds for its diameter. In particular, for the Payley tournament ${\vec{C}}_7(1,2,4)$, also known as $S{T}_7$, we prove that ${\mathcal{D}}_k({\vec{C}}_7(1,2,4))$ is connected and has diameter 8, for each $k\ge 3$.

arXiv comment21 pages, 3 figures, 1 table