The Dichromatic Number of Infinite Families of Circulant Tournaments

The dichromatic number $dc(D)$ of a digraph $D$ is defined to be the minimum number of colors such that the vertices of $D$ can be colored in such a way that every chromatic class induces an acyclic subdigraph in $D$. The cyclic circulant tournament is denoted by $ T= \vec{C}_{2n+1}(1,2,…,n) $, where $ V (T) = \mathbb{ℤ}_{2n+1}$ and for every jump $ j \in {1, 2, . . ., n} $ there exist the arcs $ (a, a + j)$ for every $ a \in \mathbb{Z}_{2n+1} $. Consider the circulant tournament $ \vec{C}_{2n+1} 〈k〉 $ obtained from the cyclic tournament by reversing one of its jumps, that is, $ \vec{C}_{2n+1} 〈k〉 $ has the same arc set as $ \vec{C}_{2n+1} (1,2,…,n) $ except for $j = k$ in which case, the arcs are $(a, a − k)$ for every $ a \in \mathbb{Z}_{2n+1} $. In this paper, we prove that $ dc (\vec{C}_{2n+1} 〈k〉 ) \in {2,3,4} $ for every $ k \in {1, 2, . . ., n} $. Moreover, we classify which circulant tournaments $ \vec{C}_{2n+1} 〈k〉 $ are vertex-critical $r$-dichromatic for every $ k \in {1, 2, . . ., n} $ and $ r \in {2, 3, 4} $. Some previous results by Neumann-Lara are generalized.