% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

\usepackage{amsfonts}
\usepackage{geometry}
\usepackage[english]{babel}
\usepackage{pstricks}
\usepackage{pstricks,pst-node}
\usepackage{color}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A Disproof of a  Neumann-Lara's Conjecture}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Bernardo Llano\thanks{Research supported by CONACYT Project CB-2012-01 178910.}\\
\small Departamento de Matem\'aticas\\[-0.8ex]
\small Universidad Aut\'onoma Metropolitana - Iztapalapa\\[-0.8ex]
\small Mexico City\\
\small\tt llano@xanum.uam.mx\\
\and
Mika Olsen \\
\small Departamento de Matem\'aticas Aplicadas y Sistemas\\[-0.8ex]
\small  Universidad Aut\'onoma Metropolitana - Cuajimalpa\\[-0.8ex]
\small Mexico City\\
\small\tt olsen@correo.cua.uam.mx
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jul 20, 2015}{XXX}\\
\small Mathematics Subject Classifications: 05C20, 05C15}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}

We disprove the following conjecture due to V\'{\i}ctor Neumann-Lara: for
every couple of integers $(r,s)$ such that $r\geq s\geq 2$, there is an
infinite set of circulant tournaments $T$ such that the dichromatic number
and the cyclic triangle free disconnection of $T$ are equal to $r$ and $s$, respectively.
Let $\mathcal{F}_{r,s}$ denote the
set of circulant tournaments $T$ with $dc(T)=r$ and $\overrightarrow{\omega }%
_{3}\left( T\right) =s$. We show that for every integer $s\geq 4$ there exists
a lower bound $b(s)$ for the dichromatic number $r$ such that $\mathcal{F}%
_{r,s}=\emptyset $
for every $r<b(s)$. We construct an infinite set of circulant tournaments $T$
such that $dc(T)=b(s)$ and $\overrightarrow{\omega }_{3}(T)=s$  and give an upper bound $B(s)$ for the
dichromatic number $r$ such that for every $r\geq B(s)$ there exists an
infinite set $\mathcal{F}_{r,s}$  of
circulant tournaments. Some infinite sets $\mathcal{F}_{r,s}$  of circulant tournaments are given for $%
b(s)<r<B(s)$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Circulant tournaments; dichromatic number; acyclic disconnection
\end{abstract}

\section{Introduction}

The dichromatic number and the acyclic (respectively, cyclic
triangle free) disconnection were introduced as measures of the
complexity of the cyclic structure of digraphs. A large value of the
dichromatic number and, oppositely, a small value of the acyclic
disconnection express a more
complex cyclic structure of a given digraph. Among other papers, see \cite%
{familia,GN,agudo,fam-inf,gendc,dc,inconn,zykov,NLU} for old and
recent results on the study of these parameters as well as open
problems. Many variations of colorings of digraphs have been
extensively studied as the oriented chromatic number and the
oriented game chromatic number. See for example \cite{NS} and
\cite{YZ}.

We define the \emph{dichromatic number} of a digraph $D$, denoted by
$dc(D),$ as the minimum number of colors in a coloring of the
vertices of $D$ such that each chromatic class induces an acyclic
subdigraph of $D$ (that is, a subdigraph containing no directed
cycles). In this terminology, the notion was introduced by V.
Neumann-Lara in \cite{dc}. Even before, the dichromatic number for
graphs and digraphs is defined by P. Erd\H{o}s in \cite{Erdos} (pp.
16--20) reporting some results obtained in a joint work with V.
Neumann-Lara. In this earlier paper, article \cite{dc} is mentioned
to be in preparation.

On the other hand, the \emph{acyclic} (respectively, \emph{cyclic
triangle free} or briefly, the
$\overrightarrow{C}_{3}$\emph{-free})\emph{\ disconnection} of a
digraph $D,$ denoted by $\overrightarrow{\omega }(D)$ (respectively,
$\overrightarrow{\omega }_{3}(D)),$ is defined to be the maximum
number of colors in a coloring of the vertices of $D$ such that no
directed cycle is properly colored (respectively, no directed
$3$-cycle is $3 $-colored). We recall that in a proper coloring of
the vertices of a digraph $D$, consecutive vertices of a directed
cycle receive different colors. A
digraph $D$ (in particular, a tournament $T$) is said to be \emph{tight} if $%
\overrightarrow{\omega }_{3}(D)=2$ (respectively, $\overrightarrow{\omega}%
_{3}(T)=2$). These definitions first appeared in \cite{inconn}.

In 1999, V. Neumann-Lara posed the following

\begin{conjecture}[\protect\cite{inconn}, Conjecture 5.8]
For every couple of integers $(r,s)$ such that $r\geq s\geq 2$,
there is an
infinite set of regular (circulant) tournaments $T$ such that $dc(T)=r$ and $%
\overrightarrow{\omega }_{3}(T)=s$ (respectively, $\overrightarrow{\omega }%
(T)=s).$
\end{conjecture}

Let $T$ be a regular tournament. We define
\begin{eqnarray}
\mathcal{F}_{r,s} &=& \{T:dc(T)=r,
\overrightarrow{\omega }_{3}\left( T\right) =s\} \quad\textup{and} \nonumber \\
\widetilde{\mathcal{F}}_{r,s} &=& \{T:dc(T)=r,\overrightarrow{\omega
}\left( T\right) =s\}. \nonumber
\end{eqnarray}

The following theorem will be useful to simplify the proofs.

\begin{theorem}[\protect\cite{simple}, Theorem 19 and Corollary 22]
Every prime circulant tournament $T$ is tight. Moreover, $\overrightarrow{%
\omega }_{3}(T)=\overrightarrow{\omega }(T)$ for every circulant tournament $%
T$. \label{teo comp tensa}
\end{theorem}

In this paper, we only deal with circulant tournaments. We notice
that in
virtue of Theorem \ref{teo comp tensa}, it suffices to consider $%
\overrightarrow{\omega }_{3}(T)$ for every circulant tournament $T$.
If some statement is valid for $\overrightarrow{\omega }_{3}(T)$ or
for a family of type $\mathcal{F}_{r,s}$, it holds for
$\overrightarrow{\omega }(T)$ or for a family of type
$\widetilde{\mathcal{F}}_{r,s}$.

In \cite{fam-inf}, the authors positively answer the conjecture for
the
special case when $r=3$ and $s=2$ giving an infinite family of $3$%
-dichromatic tight regular \emph{not} circulant tournaments$.$
However, in this paper the conjecture is disproved in general. We
show that for every integer $s\geq 4$ there exists a lower bound
$b(s)$ for the dichromatic number $r$ such that
$\mathcal{F}_{r,s}=\emptyset $ for every $r<b(s)$. We construct an
infinite set of circulant tournaments $T$ such that $dc(T)=b(s)$ and
$\overrightarrow{\omega }_{3}(T)=s$. All this is summarized in the
main theorem of this paper (see the proof in Section 4).

\begin{theorem}\label{cota inf}
Let $T$ be a circulant tournament such that $dc(T)=r$ and $\overrightarrow{\omega }_{3}(T)=s$ $(2\leq s\leq r)$. Let $b\left(
s\right) =D_{s-1}$, where $D_{s}=\left\lceil\frac{3}{2}D_{s-1}\right\rceil $ ($s\geq 2$ and $D_{1}=2$). Then
$$r\ge b( s) =\left\lceil \frac{3}{2}D_{s-2}\right\rceil
=\left\lfloor K\left( \frac{3}{2}\right)^{s-1}\right\rfloor,$$
where $K\approx1.62227$ is an irrational number. Moreover, $\left\{
\overrightarrow{C}_{3}^{s-2}\left[ \alpha \right] ,\alpha \in \mathcal{F}%
_{2,2}\right\} $ is an infinite set of $r$-dichromatic circulant
tournaments
such that $\overrightarrow{\omega }_{3}\left( \overrightarrow{C}%
_{3}^{s-2}\left[ \alpha \right] \right) =s$ and $r=b(s)$.
\end{theorem}

We give an upper bound $B(s)$ for the dichromatic number $r$ such
that for every $r\geq B(s)$ there exists an infinite set
$\mathcal{F}_{r,s}$  of
circulant tournaments (see Proposition \ref{cota sup}). Some infinite sets $%
\mathcal{F}_{r,s}$  of circulant tournaments are given for
$b(s)<r<B(s).$ The construction of the remaining cases in this
interval is an open problem since the tools used in the paper do not
apply for them.

Our proofs are strongly based on the techniques developed in
\cite{zykov}. For the usual terminology on digraphs and tournaments
used in the paper, see \cite{torneos,Bondy,Reid}.

An extended abstract of some parts of this work, with no proofs,
appeared in \cite{lagos}.

\section{Preliminaries}

Let $D=(V,A)$ be a digraph. For any $v\in V(D)$ we denote by $N^{+}(v)$ or $%
N^{+}(v,D)$ and $N^{-}(v)$ or $N^{-}(v,D)$ the out- and in-neighborhood of $%
v $ in $D$, respectively. A digraph $D$ is said to be \emph{acyclic}
if $D$ contains no directed cycles. A subset $S\subseteq V(D)$ is
\emph{acyclic} if the induced subdigraph $D\langle S\rangle $ of $D$
by the set $S$ is acyclic. The maximum cardinality of an acyclic set
of vertices of $D$ is denoted by $\beta (D).$

An $r$-coloring $\varphi :V(D)\rightarrow \{1,2,...,r\}$ of a
digraph $D$ is
a surjective function. A subdigraph $D^{\prime }$ of $D$ is \emph{%
heterochromatic} or \emph{rainbow} if every pair of vertices of
$D^{\prime }$ receive different colors under $\varphi .$ A
subdigraph $D^{\prime }$ of $D$ is \emph{properly colored }if every
pair of adjacent vertices of $D^{\prime } $ receive different colors
under $\varphi .$ A subset $S$ of vertices of $D$ that receive the
same color under $\varphi $ is called a \emph{chromatic class} and
it is a \emph{singleton} if $\left\vert S\right\vert =1.$ We say
that a $r$-coloring $\varphi $ of a digraph $D$ is $\overrightarrow{C}_{3}$%
\emph{-free} (respectively, $\overrightarrow{C}$-\emph{free}) if $D$
contains no rainbow cyclic triangles (respectively, no properly
colored directed cycles).

Let $D$ and $F$ be digraphs and $\{F_{v}\}_{v \in V(D)}$ a family of
mutually disjoint isomorphic copies of $F$. The \emph{composition} (or \emph{%
lexicographic product} $D\circ F$) $D[F]$ of the digraphs $D$ and
$F$ is
defined by $V(D[F])=\bigcup_{v\in V(D)}V(F_{v})$ and%
\[
A(D[F])= \Big[ \bigcup_{v\in V(D)}A(F_{v}) \Big] \cup \big\{
(i,j):i\in V(F_{v}),\text{ }j\in V(F_{w})\text{ and }(v,w)\in A(D)
\big\}.
\]

It is easy to prove (and left to the reader) that the composition of
digraphs is an associative but not a commutative operation.

Let $\mathbb{Z}_{2m+1}$ be the cyclic group of integers modulo $2m+1$ $%
(m\geq 1)$ and $J$ a nonempty subset of $\mathbb{Z}_{2m+1}\setminus
\{0\}$
such that $\left\vert \{-j,j\}\cap J\right\vert =1$ for every $j\in \mathbb{Z%
}_{2m+1}\setminus \{0\}$ (and therefore $\left\vert J\right\vert
=m).$ A
\emph{circulant} (or \emph{rotational}) \emph{tournament} $\overrightarrow{C}%
_{2m+1}(J)$ is defined by
$V(\overrightarrow{C}_{2m+1}(J))=\mathbb{Z}_{2m+1}$
and%
\[
A(\overrightarrow{C}_{2m+1}(J))=\left\{ (i,j):i,j\in
\mathbb{Z}_{2m+1}\text{ and }j-i\in J\right\} .
\]

Recall that the circulant tournaments are regular and their automorphism
groups are vertex--transitive. Let $[m]=\{1,2,...,m\}.$ We denote by $%
\overrightarrow{C}_{2m+1}\left\langle \emptyset \right\rangle $ and $%
\overrightarrow{C}_{2m+1}\left\langle j\right\rangle $ the circulant
tournaments $\overrightarrow{C}_{2m+1}(J)$ where $J=[m]$ and $%
J=([m]\diagdown \{j\})\cup \{-j\}$, respectively.

Observe that
$\overrightarrow{C}_{3}=\overrightarrow{C}_{3}\left\langle
\emptyset \right\rangle $. Moreover, $\overrightarrow{C}_{3}\in \mathcal{F}%
_{2,2}$.

\begin{proposition}[\protect\cite{inconn}, Proposition 3.3]
The composition of two circulant tournaments is a circulant
tournament.
\end{proposition}

The above proposition holds for circulant digraphs in general. A
(circulant) tournament $T$ is \emph{prime} (or \emph{simple}) if it
is not isomorphic to a composition of (circulant) tournaments.

\begin{proposition}[\protect\cite{NLU}, Theorem 1]
Let $m\in \mathbb{N}$. Then
$dc(\overrightarrow{C}_{2m+1}\left\langle \emptyset \right\rangle
)=2.$ \label{dcNLU}
\end{proposition}

\begin{proposition}[\protect\cite{inconn}, Proposition 4.4(i), Theorem 4.11]

Let $m\in \mathbb{N}$.

\begin{enumerate}
\item[\emph{(i)}] $\overrightarrow{\omega }_{3}(\overrightarrow{C}%
_{2m+1}\left\langle \emptyset \right\rangle )=\overrightarrow{\omega }(%
\overrightarrow{C}_{2m+1}\left\langle \emptyset \right\rangle
)=2.$

\item[\emph{(ii)}] $\overrightarrow{\omega }_{3}(\overrightarrow{C}%
_{2m+1}\left\langle m-1\right\rangle )=\overrightarrow{\omega }(%
\overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle )=2.$
\label{w3NL}
\end{enumerate}
\end{proposition}

We use the following definition taken from {\cite{inconn}}. A
digraph $D$
will be said to be $\overrightarrow{\omega }$-\emph{keen} (respectively, $%
\overrightarrow{\omega }_{3}$-\emph{keen}) if there is an optimal coloring $%
\varphi $ of $V(D)$ (that is, it uses the maximum number of colors),
with no
properly colored directed cycles (respectively, with no $3$-colored $%
\overrightarrow{C}_{3}$) of $D$, having exactly one singleton
chromatic class. Notice that no optimal coloring $\varphi $ of
$V(D)$ leaves more than one such a class.

\begin{lemma}[\protect\cite{simple}, Theorems 17,18]
\label{agudo} Every circulant tournament is $\overrightarrow{\omega }_{3}$%
-keen (respectively, $\overrightarrow{\omega }$-keen).
\end{lemma}

This lemma was an important tool to prove Theorem \ref{teo comp
tensa} in \cite{simple}. It will be later used in other proofs of the paper.


\section{Infinite sets of $r$-dichromatic circulant tournaments for every $r\geq 2$ and $s=2$}

This section is devoted to the construction of infinite families of circulant tournaments $T$ such that $dc(T)=r$ and
$\overrightarrow{\omega }_{3}(T)=2$ (that is, tight circulant tournaments), where $r\geq2$.

Let $\overrightarrow{C}_{n\left( p+1\right) +1}\left( J\right) $ be the set
of circulant tournaments defined in \cite{familia}, where
\begin{eqnarray*}
J &=& \left\{ 1,2,\ldots ,p\right\} \cup \left\{ p+2,p+3,\ldots ,2p-t\right\} \cup  \\
 & & \hspace{1cm} \left\{ 2p+3,\ldots ,3p-2t\right\} \cup \ldots \cup \left\{ \left(n-1\right) p+n\right\} \\
  &=& \bigcup_{i=0}^{n-1} \big\{ ip+(i+1), \ldots, ip+p-it \big\}
\end{eqnarray*}
and $p=\left( n-1\right) \left( t+1\right) +1$, $n\geq 2,$ $t\geq 0.$

To understand the structure of these tournaments it is convenient to
establish a one to one correspondence between the out-neighborhood of a
vertex and the following subset $H_{p,t}$ of entries $m_{ij}$ in a $%
M_{n\times \left( p+1\right) }$ matrix:
\begin{equation*}
H_{p,t}=\left\{ m_{ij}\in M_{n\times \left( p+1\right) }:\left( i-1\right)
\left( t+1\right) +j\leq p\right\}.
\end{equation*}%
Let $v\in V(\overrightarrow{C}_{n\left( p+1\right) +1}\left( J\right) ) $, and $i,j\in \mathbb{N}$ such that $v=\left(
p+1\right) \left( i-1\right) +j$, with $1\leq i\leq n$ and $1\leq j\leq p$.
The function $\psi : N^{+}(v) \rightarrow $ $H_{p,t}$ defined by $%
\psi \left( w\right) =m_{ij}$ is clearly a bijection. Since $\overrightarrow{C}_{n\left( p+1\right) +1}\left( J\right) $
is vertex-transitive, we have that  $J=N^{+}(0)$. Let $\mathbf{H}_{p,t}$ be the
induced subtournament by $N^{+}(0)$ in $\overrightarrow{C}_{n\left(
p+1\right) +1}\left( J\right)$. Notice that the
induced subtournament by $N^{+}(v)$ is isomorphic to $\mathbf{H}_{p,t}$ for every $v\in V(\overrightarrow{C}_{n\left( p+1\right) +1}\left( J\right) ) $.

We define the out-neighborhood of each vertex $m_{ij}\in $ $H_{p,t}$ as the
union of three disjoint sets of vertices in $H_{p,t},$ specifically $%
N^{+}\left( m_{ij},\mathbf{H}_{p,t}\right) =A_{ij}\cup B_{ij}\cup C_{ij}$,
where
\begin{equation*}
\begin{array}{lc}
A_{ij} =\{m_{kl}\in M_{n\times (p+1)}:(k-1)(s+1)+l-j\leq (i-2)(s+1), & \\ \hspace{2in} k\geq
1,l\geq j\}, \\
B_{ij} =\{m_{kl}\in M_{n\times (p+1)}:(k-i)(s+1)+l-j-1<(n-i)(s+1)-j+r, & \\ \hspace{2in} k
\geq i,l\geq j+1\}, \\
C_{ij} =\{m_{kl}\in M_{n\times (p+1)}:(k-i-1)(s+1)+l-1\leq j-2, & \\ \hspace{2in} k\geq
i+1,l\geq 1\}.
\end{array}
\end{equation*}

By Lemma 1 of \cite{familia}, the subtournaments induced by $A_{ij}$, $B_{ij}$ and $C_{ij}$ are
the vertex-disjoint tournaments $\mathbf{H}_{1+(i-2)(t+1),t}$, $\mathbf{H}_{p-(i-1)(t+1)-j,t}$ and $\mathbf{H}_{j-1,t}$, respectively.
%
In the next figure, the entry $m_{4,8}$ is the point $\ast $, the vertices in
the out-neighborhood of $\ast $ in $\mathbf{H}_{22,2}$ are the $\bullet $
points partitioned into the sets $A_{4,8},$ $B_{4,8}$ and $C_{4,8}$ (the
triangles that appear at the top, to the right and to the left of $\ast ,$
respectively). Notice that the vertices in the in-neighborhood of $\ast $ in $%
\mathbf{H}_{22,2}$ are the $\circ $ points and the $\cdot $ and $\triangle $
points are not vertices of $\mathbf{H}_{22,2}$. \bigskip
\begin{equation*}
\begin{array}[t]{ccccccccccccccccccccccc}
\circ & \circ & \circ & \circ & \circ & \circ & \circ & \bullet & \bullet &
\bullet & \bullet & \bullet & \bullet & \bullet & \circ & \circ & \circ &
\circ & \circ & \circ & \circ & \circ & \triangle \\
\circ & \circ & \circ & \circ & \circ & \circ & \circ & \bullet & \bullet &
\bullet & \bullet & \circ & \circ & \circ & \circ & \circ & \circ & \circ &
\circ & \bigtriangleup & \cdot & \cdot & \cdot \\
\circ & \circ & \circ & \circ & \circ & \circ & \circ & \bullet & \circ &
\circ & \circ & \circ & \circ & \circ & \circ & \circ & \bigtriangleup &
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\circ & \circ & \circ & \circ & \circ & \circ & \circ & \ast & \bullet &
\bullet & \bullet & \bullet & \bullet & \bigtriangleup & \cdot & \cdot &
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \circ
& \bullet & \bullet & \bigtriangleup & \cdot & \cdot & \cdot & \cdot & \cdot
& \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\bullet & \bullet & \bullet & \bullet & \circ & \circ & \circ &
\bigtriangleup & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot &
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\bullet & \circ & \circ & \circ & \bigtriangleup & \cdot & \cdot & \cdot &
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot
& \cdot & \cdot & \cdot & \cdot & \cdot \\
\circ & \bigtriangleup & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot &
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot
& \cdot & \cdot & \cdot & \cdot & \cdot%
\end{array}%
\end{equation*}%
\begin{equation*}
\text{The tournament }\mathbf{H}_{22,2}\text{ and the out-neighborhood of }%
m_{ij}=m_{4,8}
\end{equation*}

\begin{lemma}[\protect\cite{familia}, Theorem 5]
$dc\left( \overrightarrow{C}_{n\left( p+1\right) +1}\left( J\right) \right)
=n+1.$ \label{7-dic}
\end{lemma}

\begin{theorem}
$\overrightarrow{C}_{n\left( p+1\right) +1}\left( J\right) $ is tight (that is,
$\overrightarrow{\omega }_{3}(\overrightarrow{C}_{n\left( p+1\right)
+1}\left( J\right) )=2$)$.$ \label{dic-tenso}
\end{theorem}

\begin{proof}
Let $T\cong \overrightarrow{C}_{n\left( p+1\right) +1}\left( J\right) $. For a
contradiction, suppose that $T$ is not tight, that is, there exists a $%
\overrightarrow{C}_{3}$-free $3$-coloring $\varphi :V\left( T\right)
\rightarrow \left\{ blue,green,red\right\} $ of $T$. By Lemma \ref{agudo}, $T$ is $%
\overrightarrow{\omega }_{3}$-keen and therefore there is exactly one
singleton chromatic class. Since $T$ is vertex-transitive, we may assume that
$\varphi \left( 0\right) =blue$, and $0$ is the only vertex of color $blue$.
Suppose that $\varphi \left( 1\right) =green$ $(\varphi (m_{11})=green$ in matrix
notation). Since $\left( 0,1,i\right) $ is a cyclic triangle for every $i\in
\left\{ kp-\left( k-1\right) t+1:1 \leq k \leq n\right\} $ (these cyclic
triangles correspond to $(0,m_{11},\bigtriangleup )$ in the matrix $%
M_{n\times \left( p+1\right) }$) and $\varphi $ is $\overrightarrow{C}_{3}$%
-free, then $\varphi \left( i\right) =green$.
Let us define
\begin{equation*}
N_{k}=\left\{ \left( k-1\right) p+k,\left( k-1\right) p+k+1,\ldots
,kp-\left( k-1\right) t\right\}
\end{equation*}%
for $1 \leq k \leq n$ $(N_{k}$ can be viewed as the set of elements $\circ $ and
$\bullet $ of the $k$-th row of the matrix $M_{n\times \left( p+1\right) }).$
Observe that $\left( 0,j,kp-\left( k-1\right) t+1\right) $ (respectively, $%
(0,\circ ,\triangle )$ or $(0,\bullet ,\triangle ))$ is a cyclic
triangle for every $j\in N_{k}$. Using again that $\varphi $ is $%
\overrightarrow{C}_{3}$-free, we have that $\varphi \left( j\right) =green$ for
every $j\in N_{k}$. Therefore $N^{+}\left( 0\right) $ is monochromatic.
Observe that $kp-\left( k-1\right) t+1\in N^{-}\left( 0\right) $ (elements of type $%
kp-\left( k-1\right) t+1$ correspond to $\triangle$ in the matrix) and $\varphi \left(
kp-\left( k-1\right) t+1\right) =green$. Analogously, we can conclude that $%
N^{-}\left( 0\right) $ is monochromatic. We have only used two colors, so $%
\varphi $ is not surjective, a contradiction to the initial assumption.
\end{proof}

Observe that $\overrightarrow{\omega }(\overrightarrow{C}_{n\left(
p+1\right) +1}\left( J\right) )=2$ by Theorem \ref{teo comp tensa}.

\begin{corollary}
For every $r\geq 2$ there exists an infinite set $\mathcal{F}_{r,2}$ of
tight $r$-dichromatic circulant tournaments. \label{r-dic-tensos}
\end{corollary}

\begin{proof}
By Propositions \ref{dcNLU} and \ref{w3NL}(i), the infinite set $\mathcal{F}%
_{2,2}=\left\{ \overrightarrow{C}_{2n+1}\left\langle \emptyset
\right\rangle :n\in \mathbb{N}\right\} $ is the desired set for $r=2.$ By
Lemma \ref{7-dic} and Theorem \ref{dic-tenso}, for every $r\geq 3$ the
infinite set
\begin{equation*}
\mathcal{F}_{r+1,2}=\left\{ \overrightarrow{C}_{r\left( p+1\right) +1}\left(
J\right) :p=\left( r-1\right) \left( t+1\right) +1,t\geq 0\right\}
\end{equation*}%
provides the remaining cases.
\end{proof}


\section{Infinite sets for $s\geq 3$}

Let $H=(V,E)$ a finite hypergraph. A hypergraph $H$ is $t$-\emph{uniform}
(or simply, a $t$-\emph{graph}) if every edge of $H$ has cardinality $t.$ A
hypergraph $H$ is called \emph{circulant} if it has an automorphism which
is a cyclic permutation of \ $V\left( H\right) $. If $t\leq m$,$\ $the
circulant $t$-graph $\Lambda _{m,t}$ is defined by $V\left( \Lambda
_{m,t}\right) =\mathbb{Z}_{m}$ and $E\left( \Lambda _{m,t}\right) =\left\{
\alpha _{j}:j\in \mathbb{Z}_{m}\right\} $ where $$\alpha _{j}=\left\{
j,j+1,\ldots ,j+t-1\right\} $$ for $j\in \mathbb{Z}_{m}$.

We denote by $\beta (T)$ the maximum cardinality of an acyclic set of vertices of a tournament $T$.
In \cite{dc} (see Theorem 8), it was proved that
$dc\left( T\left[ U\right] \right) \geq dc\left( T\right) + dc\left( U\right) -1$. Using this result as well as
Propositions 32(iii) and 34 and Corollary 43 of \cite{zykov}, it is not hard to establish the following proposition
that will be useful in the proof of Theorem \ref{cota inf}.

\begin{proposition}
\label{zykov dicr 2} Let $T$ and $U$ be circulant tournaments such that $T$ has order $2m+1$
 and $U$ is an $r$-dichromatic tournament. Then
\begin{equation*}
dc\left( T\left[ U\right] \right) \geq \left\lceil \frac{r\left( 2m+1\right)
}{m+1}\right\rceil .
\end{equation*}%
Moreover, if $\beta \left( T\right) =t$ and $T$ contains an isomorphic copy
of a $t$-graph $\Lambda _{2m+1,t}$ (where $ V\left( \Lambda
_{2m+1,t}\right) =\mathbb{Z}_{2m+1}$, $E\left( \Lambda _{2m+1,t}\right) =\left\{
\alpha _{j}:j\in \mathbb{Z}_{2m+1}\right\} $, $\alpha _{j}=\left\{
j,j+1,\ldots ,j+t-1\right\} $ and sums are taken modulo $2m+1$), then%
\begin{equation*}
dc\left( T\left[ U\right] \right) =\left\lceil \frac{r\left( 2m+1\right) }{t}%
\right\rceil .
\end{equation*}
\end{proposition}

\begin{proposition}[\protect\cite{inconn}, Proposition 3.6(i)]
\label{zykov inconn} Let $T$ be a $\overrightarrow{\omega }_{3}$-keen (respectively, $\overrightarrow{\omega }  $-keen)
tournament and $U$ an arbitrary tournament. Then
\begin{eqnarray*}
\overrightarrow{\omega }_{3}\left( T\left[ U\right] \right) &=&%
\overrightarrow{\omega }_{3}\left( T\right) +\overrightarrow{\omega }%
_{3}\left( U\right) -1 \\
(\overrightarrow{\omega }\left( T\left[ U\right] \right) &=&\overrightarrow{%
\omega }\left( T\right) +\overrightarrow{\omega }\left( U\right) -1).
\end{eqnarray*}
\end{proposition}

\begin{proposition}[\protect\cite{Cota}, Corollary 1]
\label{prop fracc} Consider the recurrence relation $D_{n}=\left\lceil \frac{%
3}{2}D_{n-1}\right\rceil $ ($n\geq 1$ and $D_{0}=1$), then
\begin{equation*}
D_{n}=\left\lfloor K\left( \frac{3}{2}\right) ^{n}\right\rfloor \quad \quad
\left( n=1,2,\ldots \right) ,
\end{equation*}%
where $K\approx 1.62227$ is an irrational number.
\end{proposition}

The previous recurrence relation appears in the solution of the legendary
Josephus Flavius problem. It is the classical case when $n$ Jews formed in a
circle decide to kill every third remaining person until no one is left (the
last survivor must commit suicide). In the story, there were $40$ Jewish
soldiers trapped in a cave by the Roman army who chose suicide rather than
be captured. For more details about the mathematical problem see \cite{Cota}.


The following proposition is a consequence of Theorem \ref{teo comp tensa}.

\begin{proposition}
\label{exist H}Let $T$ be a circulant tournament with $\overrightarrow{\omega }_{3}\left( T\right) =s\geq 3$. 
There exist $s-1$ tight circulant tournaments $T_{1},T_{2},\ldots ,T_{s-1}$ such that 
$T\cong T_{1}\left[ T_{2}\left[ \ldots \left[ T_{s-1}\right] \right] \right] $.
\end{proposition}

\begin{proof} We proceed by induction on $s$.
If $s=3$, then by Theorem \ref{teo
comp tensa}, $T$ is a composition of two circulant tournaments $T_{1}$ and $T_{2}$,
that is, $T\cong T_{1}[T_{2}]$. Observe that if
$\overrightarrow{\omega }_{3}(T_{1})=s_{1}\geq 2$ and
$\overrightarrow{\omega }_{3}(T_{2})=s_{2}\geq 2$, then
\begin{equation*}
\overrightarrow{\omega }_{3}(T_{1}[T_{2}])=s_{1}+s_{2}-1=3,
\end{equation*}%
$s_{1}=s_{2}=2$ and both $T_{1}$  and $T_{2}$ are tight circulant tournaments.

Suppose that the claim is valid for every $3\leq \overrightarrow{\omega }_{3}(T)=s^{\prime }<s$. By
the induction hypothesis, there exist $s^{\prime }-1$ tight circulant
tournaments $T_{1},T_{2},\ldots ,T_{s^{\prime }-1}$ such that 
$$T \cong T_{1}[T_{2}[\ldots \lbrack T_{s^{\prime }-1}]]].$$
Let $\overrightarrow{\omega }_{3}(T)=s$. Hence, $T$ is a composition of two
circulant tournaments $U$ and $W$, that is $T\cong U[W]$. Let $\overrightarrow{%
\omega }_{3}(U)=t_{1}\geq 2$ and $\overrightarrow{\omega }_{3}(W)=t_{2}\geq
2 $.
Since
\begin{displaymath}
3\leq \overrightarrow{\omega }_{3}(U[W])=t_{1}+t_{2}-1=s,
\end{displaymath}
then $2\leq t_{1}<s$ and $2\leq t_{2}<s$. By the induction hypothesis, there exist $t_{1}-1$
tight circulant tournaments $U_{1},U_{2},\ldots ,U_{t_{1}-1}$ such that $%
U\cong U_{1}[U_{2}[\ldots \lbrack U_{t_{1}-1}]]]$, and $t_{2}-1$ tight
circulant tournaments $W_{1},W_{2},\ldots ,W_{t_{2}-1}$ such that $W\cong
W_{1}[W_{2}[\ldots \lbrack W_{t_{2}-1}]]]$, then%
\begin{equation*}
T\cong U[W]\cong (U_{1}[U_{2}[\ldots \lbrack
U_{t_{1}-1}]]])[W_{1}[W_{2}[\ldots \lbrack W_{t_{2}-1}]]]].
\end{equation*}%
Using the associative property of the composition, we have that
\begin{equation*}
T\cong U_{1}[U_{2}[\ldots \lbrack U_{t_{1}-1}[W_{1}[W_{2}[\ldots \lbrack
W_{t_{2}-1}]]]]]]].
\end{equation*}%
Therefore, $T$ is the composition of $t_{1}-1+t_{2}-1=s-1$ tight circulant
tournaments.
\end{proof}

Let $s\in \mathbb{N}$ and define $\overrightarrow{C}_{3}^{1}=\overrightarrow{%
C}_{3}$ and $\overrightarrow{C}_{3}^{s}=\overrightarrow{C}_{3}\left[
\overrightarrow{C}_{3}^{s-1}\right] $ for every $s\geq 2$. Observe that in
virtue of Proposition \ref{zykov inconn} and Lemma \ref{agudo}, $\overrightarrow{%
\omega }_{3}\left( \overrightarrow{C}_{3}^{s}\right) =s+1$.

We prove the main theorem of this paper.

\begin{proof} (\textbf{Theorem \ref{cota inf}})

Let $U$ be an $r$-dichromatic tournament. Since the composition of tournaments is associative and by the first
inequality of Proposition \ref{zykov dicr 2}, we have that
\begin{equation*}
dc\left( T\left[ U\right] \right) \geq \left\lceil \frac{r\left( 2m+1\right)
}{m+1}\right\rceil .
\end{equation*}%
Therefore
\begin{displaymath}
dc\left( T\left[ U\right] \right) \geq \left\lceil 2r-\dfrac{r}{%
m+1}\right\rceil \geq \left\lceil \frac{3}{2}r\right\rceil.
\end{displaymath}
It follows that $dc\left( T\left[ U\right]\right) \geq \left\lceil \frac{3}{2}r\right\rceil $
for every $r$-dichromatic tournament $U$.

Now let $T$ be a circulant tournament such that $\overrightarrow{\omega }%
_{3}\left( T\right) =s$. By Proposition \ref{exist H}, there exist $%
T_{1},T_{2},\ldots ,T_{s-1}$ such that $T\cong T_{1}\left[ T_{2}\left[
\ldots \left[ T_{s-1}\right] \right] \right] $. Let $dc\left( T_{s-1}\right)
=r\geq 2=\left\lceil \frac{3}{2}\right\rceil $, then
\begin{equation*}
dc\left( T\right) \geq \underset{s-2}{\underbrace{\left\lceil \frac{3}{2}%
\left\lceil \frac{3}{2}\left\lceil \ldots \left\lceil \frac{3}{2}%
r\right\rceil \right\rceil \right\rceil \right\rceil }}\geq \underset{s-1}{%
\underbrace{\left\lceil \frac{3}{2}\left\lceil \frac{3}{2}\left\lceil \ldots
\left\lceil \frac{3}{2}\right\rceil \right\rceil \right\rceil \right\rceil }}%
=D_{s-1}.
\end{equation*}
By Proposition \ref{prop fracc}, $dc\left( T\right) \geq \left\lfloor
K\left( \frac{3}{2}\right) ^{s-1}\right\rfloor $.

Let $T\in \left\{ \overrightarrow{C}_{3}^{s-2}\left[ \alpha \right] ,\alpha
\in \mathcal{F}_{2,2}\right\} $. Since $\overrightarrow{C}_{3}$ and $\alpha $
are tight, then $\overrightarrow{\omega }_{3}\left( T\right) =s$. Observe that $%
2=\left\lceil \frac{3}{2}\right\rceil $, then
\begin{equation*}
dc\left( T\right) =\underset{s-1}{\underbrace{\left\lceil \frac{3}{2}%
\left\lceil \frac{3}{2}\left\lceil \ldots \left\lceil \frac{3}{2}%
\right\rceil \right\rceil \right\rceil \right\rceil }}=D_{s-1}.
\end{equation*}%
By Proposition \ref{prop fracc}, $dc\left( T\right) =\left\lfloor K\left(
\frac{3}{2}\right) ^{s-1}\right\rfloor =b(s)$.
\end{proof}

\begin{remark}
Notice that $b(s)$ is a lower bound for $dc(T)=r$ when $\overrightarrow{\omega
}_{3}(T)=s$ and there are no $r$-dichromatic circulant tournaments for which
$r<b(s).$
\end{remark}


Let $D$ be a digraph. The hypergraph $H_{1}(D)$ is defined by $%
V(H_{1}(D))=V(D)$ and
\begin{equation*}
E(H_{1}(D))=\{U\subseteq V(D):U\text{ is a maximal acyclic set}\}.
\end{equation*}

\begin{lemma}[\protect\cite{zykov}, Proposition 41(i)]
Let $m\geq 2$. Then

\begin{enumerate}
\item[\emph{(i)}] $H_{1}(\overrightarrow{C}_{2m+1}\left\langle \emptyset
\right\rangle )\supseteq \Lambda _{2m+1,m+1}$ and

\item[\emph{(ii)}] $\beta (\overrightarrow{C}_{2m+1}\left\langle
\emptyset \right\rangle )=m+1.$ \label{beta-de-ciclico}
\end{enumerate}
\end{lemma}

We prove a similar result to the previous lemma for the family of circulant tournaments 
$\overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle$ with $m\geq 2$.

\begin{lemma}
Let $m\geq 2$. Then

\begin{enumerate}
\item[\emph{(i)}] $H_{1}(\overrightarrow{C}_{2m+1}\left\langle
m-1\right\rangle )\supseteq \Lambda _{2m+1,m-1}$ and

\item[\emph{(ii)}] $\beta (\overrightarrow{C}_{2m+1}\left\langle
m-1\right\rangle )=m-1.$ \label{beta-de-m-1}
\end{enumerate}
\end{lemma}

\begin{proof}
(i) Since $\overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle $ is
vertex-transitive and $\left\{ 0,1,\ldots ,m-2\right\} $ is an acyclic
vertex subset of cardinality $m-1$, the inclusion is valid.

(ii) Clearly, $\beta (\overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle
)\geq m-1$. Let $U$ be a vertex set of maximum cardinality, such that $%
\left\langle U\right\rangle $ is isomorphic to the acyclic subtournament of
order $\left\vert U\right\vert $. Since $\overrightarrow{C}%
_{2m+1}\left\langle m-1\right\rangle $ is a vertex-transitive tournament, we
may assume that $0$ is the source of $U$. In the out-neighborhood of $0$ we
have the following sequence:
\begin{eqnarray*}
N^{+}\left( 1\right) &=&\left\{ 2,3,\ldots ,m-2\right\}, \\
N^{+}\left( 2\right) &=&\left\{ 3,4,\ldots ,m-2,m,m+2\right\}, \\
N^{+}\left( 3\right) &=&\left\{ 4,5,\ldots ,m-2,m\right\}, \\
N^{+}\left( 4\right) &=&\left\{ 5,6,\ldots ,m-2,m,m+2\right\}, \\
&&\vdots \\
N^{+}\left( m-2\right) &=&\left\{ m,m+2\right\}, \\
N^{+}\left( m\right) &=&\left\{ 1,m+2\right\}, \\
N^{+}\left( m+2\right) &=&\left\{ 1,3\right\}.
\end{eqnarray*}%
Therefore, if $\left\vert U\right\vert \geq m$,$\ $the second source is $2$,
and $U=\left\{ 0,2,3,\ldots ,m-2,m,m+2\right\} .$ But $\left(m+2,3,4,m+2\right) $ is a cyclic triangle in 
$\overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle $. 
Hence, it follows that $\beta (\overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle )=m-1.$
\end{proof}

As a consequence of the second equality of Proposition \ref{zykov dicr 2}
and Lemma \ref{beta-de-m-1}, we have the following

\begin{corollary}
Let $\alpha $ be a $r$-dichromatic tournament, then
\begin{equation*}
dc\left( \overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle \left[
\alpha \right] \right) =\left\lceil \frac{r \, \left( 2m+1\right) }{m-1}%
\right\rceil .
\end{equation*}%
Moreover, if $m\geq 3r+1$, then $dc\left( \overrightarrow{C}%
_{2m+1}\left\langle m-1\right\rangle \left[ \alpha \right] \right) =2r+1$. %
\label{coro-comp}
\end{corollary}

In what follows, we will recursively construct  $r$-dichromatic circulant
tournaments with fixed $\overrightarrow{C}_{3}$-free\ disconnection. For this purpose, we define the following functions
that will describe the growth of the dichromatic number by the composition of
circulant tournaments.

Let $f_{i}^{\prime}$, $f_{i}$ $:$ $\mathbb{N}^{2}\rightarrow \mathbb{N}$
$(i \in \{0,1,2\})$ be functions defined by
\begin{displaymath}
\begin{array}{lll}
f_{0}^{\prime }(q,m)=q(m+1)-1, & f_{0}(q,m)=q(2m+1)-1 & (q\geq 1,m\geq 2), \\
f_{1}^{\prime }(q,m)=qm+1, & f_{1}(q,m)=q(2m+1)+3 & (q\geq 1,m\geq 3), \\
f_{2}^{\prime }(q,m)=2q+m, & f_{2}(q,m)=3q+m+1 & (q\geq 1,m\in \{1,2\}).
\end{array}
\end{displaymath}


We define the (infinite) digraphs $D_{i}$ for $i \in \{0,1,2\}$ as follows:%
\begin{eqnarray*}
V\left( D_{i}\right) &=&\left\{ v\in \mathbb{N}:v\geq 3\right\} , \\
A\left( D_{i}\right) &=&\left\{ \left( f_{i}^{\prime }\left( q,m\right)
,f_{i}\left( q,m\right) \right) \right\} .
\end{eqnarray*}

Let $D=D_{0}\cup D_{1}\cup D_{2}.$ Clearly, $D_{0},$ $D_{1}$ and $D_{2}$ are
arc-disjoint and acyclic. We emphasize that $(u,v)\in A(D)$ if and only if $%
u=f_{i}^{\prime }\left( q,m\right) $ and $v=f_{i}\left( q,m\right) $ $%
(i \in \{0,1,2\})$ for some positive integers $q$ and $m$ such that $q\geq 1$ and

\begin{enumerate}
\item[(i)] $m\geq 2$ if $i=0,$

\item[(ii)] $m\geq 3$ if $i=1$ and

\item[(iii)] $1\leq m\leq 2$ if $i=2.$
\end{enumerate}

Furthermore, if $T$ is an $r^{\prime }$-dichromatic tournament with $%
r^{\prime }=f_{i}^{\prime }\left( q,m\right) $, then $W_{i}[T]$ is an $r$%
-dichromatic tournament with $r=f_{i}\left( q,m\right) $ $(i \in \{0,1,2\})$, where $%
W_{0}\cong \overrightarrow{C}_{2m+1}\left\langle \emptyset \right\rangle ,$
$W_{1}\cong \overrightarrow{C}_{2m+1}\left\langle m\right\rangle $ and $%
W_{2}\cong \overrightarrow{C}_{3}.$ Finally, if $r\equiv 1$(mod $3$), then
by the definition of $f_{2}(q,m)$ it follows that $dc\left( \overrightarrow{C%
}_{3}[T]\right) \neq r$ for every tournament $T.$

We point out that $f_{i},$ $f_{i}^{\prime }$ and $D_{i}$ for $i \in \{0,1\}$ were
defined by V. Neumann-Lara in \cite{zykov}, where more details can be found.

\begin{lemma}[\protect\cite{zykov}, Lemma 64]
For each positive integer $n\geq 3$, $n\neq 7,$ there is a directed path in $%
D=D_{0}\cup D_{1}$ from a vertex in $S=\left\{ 3,4,5,11,15,23\right\} $ to $%
n $. \label{directed-path}
\end{lemma}

\begin{lemma}
For each positive integer $n\geq 3,$ there is a directed path in $%
D=D_{0}\cup D_{1}\cup D_{2}$ from a vertex in $S=\left\{ 3,4,5,7\right\} $
to $n$. \label{directed-path2}
\end{lemma}

\begin{proof}
A consequence of Lemma \ref{directed-path} and observing that $(7,11),(10,15),(15,23) \subset A(D_{2})$
and $(7,13)\in A(D_{0}).$ Note that by Lemma \ref{7-dic}, we have that $\overrightarrow{C}_{30t+43}(J)$ is a $7$-dichromatic
tournament for every $t\geq 0.$
\end{proof}

\begin{proposition}
Let $r\geq 2$ and $s\geq 2.$ Then

\begin{enumerate}
\item[\emph{(i)}] $\mathcal{F}_{2r,s+1}=\left\{ \overrightarrow{C}%
_{2r+1}\left\langle \emptyset \right\rangle \left[ \alpha \right] :\alpha
\in \mathcal{F}_{r,s}\right\} .$

\item[\emph{(ii)}] $\mathcal{F}_{2r+1,s+1}=\left\{ \overrightarrow{C}%
_{2(3r+1)+1}\left\langle 3r\right\rangle \left[ \alpha \right] :\alpha \in
\mathcal{F}_{r,s}\right\} .$

\item[\emph{(iii)}] $\mathcal{F}_{3r,s+1}=\left\{ \overrightarrow{C}_{3}%
\left[ \alpha \right] :\alpha \in \mathcal{F}_{2r,s}\right\} $.

\item[\emph{(iv)}] $\mathcal{F}_{3r+2,s+1}=\left\{ \overrightarrow{C}_{3}%
\left[ \alpha \right] :\alpha \in \mathcal{F}_{2r+1,s}\right\} $. \label%
{F-123}
\end{enumerate}
\end{proposition}

\begin{proof}
We proceed case by case.

\begin{enumerate}
\item[(i)] Let $\alpha \in \mathcal{F}_{r,s}.$ By Proposition \ref{zykov
dicr 2} and Lemma \ref{beta-de-ciclico}, if $r\leq m,$ then
\begin{equation*}
dc\left( \overrightarrow{C}_{2m+1}\left\langle \emptyset \right\rangle \left[
\alpha \right] \right) =\left\lceil \frac{r(2m+1)}{m+1}\right\rceil
=\left\lceil 2r-\frac{r}{m+1}\right\rceil =2r.
\end{equation*}%
%In this case $m=r.$ By Propositions \ref{zykov inconn} and \ref{w3NL}(i), we have that 
Hence, $m=r$ and by Propositions \ref{zykov inconn} and \ref{w3NL}(i),  
$\overrightarrow{\omega }_{3}\left( \overrightarrow{C}_{2r+1}\left\langle \emptyset \right\rangle \left[ \alpha \right] \right)
=s+1.$

\item[(ii)] Let $\alpha \in \mathcal{F}_{r,s}.$ By Corollary \ref{coro-comp}%
, if $m\geq 3r+1,$ then
\begin{equation*}
dc\left( \overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle \left[
\alpha \right] \right) =2r+1.
\end{equation*}%
In this case the equality holds. By Proposition \ref{w3NL}(ii) and Lemma \ref%
{beta-de-m-1},
\begin{equation*}
\overrightarrow{\omega }_{3}\left( \overrightarrow{C}_{2m+1}\left\langle
m-1\right\rangle \left[ \alpha \right] \right) =s+1.
\end{equation*}

\item[(iii)] Let $\alpha \in \mathcal{F}_{2r,s}.$ By Proposition \ref{zykov
dicr 2}, $dc\left( \overrightarrow{C}_{3}\left[ \alpha \right] \right)
=\left\lceil \frac{2r\cdot 3}{2}\right\rceil =3r.$ On the other hand, since $%
\overrightarrow{C}_{3}\in \mathcal{F}_{2,2},$ $\overrightarrow{\omega }%
_{3}\left( \overrightarrow{C}_{3}\left[ \alpha \right] \right) =s+1.$

\item[(iv)] Let $\alpha \in \mathcal{F}_{2r+1,s}.$ By Proposition \ref{zykov
dicr 2}, $dc\left( \overrightarrow{C}_{3}\left[ \alpha \right] \right)
=\left\lceil \frac{(2r+1)\cdot 3}{2}\right\rceil =3r+2.$ On the other hand,
since $\overrightarrow{C}_{3}\in \mathcal{F}_{2,2},$ $\overrightarrow{\omega
}_{3}\left( \overrightarrow{C}_{3}\left[ \alpha \right] \right) =s+1.$
\end{enumerate}
\end{proof}

\begin{proposition}
\label{inconn 3}For every integer $r\geq 3$ there is an infinite set of
circulant tournaments $T$ such that $dc\left( T\right) =r$ and $%
\overrightarrow{\omega }_{3}\left( T\right) =3$.
\end{proposition}

\begin{proof}
By Theorem \ref{cota inf} and Lemma \ref{directed-path2}, we can construct
the infinite sets $\mathcal{F}_{r,3}$ for $r=6$ and $r\geq 8$.

Let $\alpha \in \mathcal{F}_{2,2}$, then
\begin{equation*}
dc\left( \overrightarrow{C}_{3}\left[ \alpha \right] \right) =\left\lceil
\frac{2\left( 3\right) }{2}\right\rceil =3\text{ and }\overrightarrow{\omega
}_{3}(\overrightarrow{C}_{3}\left[ \alpha \right] )=2+2-1=3.
\end{equation*}%
Therefore $\mathcal{F}_{3,3}=\left\{ \overrightarrow{C}_{3}\left[ \alpha %
\right] :\alpha \in \mathcal{F}_{2,2}\right\} .$

Let $\alpha \in \mathcal{F}_{2,2}$, then
\begin{equation*}
dc\left( \overrightarrow{C}_{5}\left\langle \emptyset \right\rangle \left[
\alpha \right] \right) =\left\lceil \frac{2\left( 5\right) }{3}\right\rceil
=4\text{ and }\overrightarrow{\omega }_{3}(\overrightarrow{C}_{3}\left[
\alpha \right] )=2+2-1=3.
\end{equation*}%
Then $\mathcal{F}_{4,3}=\left\{ \overrightarrow{C}_{5}\left\langle \emptyset
\right\rangle \left[ \alpha \right] :\alpha \in \mathcal{F}_{2,2}\right\} .$

Analogously,
\begin{equation*}
\begin{array}{cc}
\mathcal{F}_{5,3}=\left\{ \overrightarrow{C}_{3}\left[ \alpha \right]
:\alpha \in \mathcal{F}_{3,2}\right\} , & \mathcal{F}_{7,3}=\left\{
\overrightarrow{C}_{7}\left\langle 3\right\rangle \left[ \alpha \right]
:\alpha \in \mathcal{F}_{3,2}\right\}%
\end{array}.
\end{equation*}%
\end{proof}

Let $B(s)$ $(s\geq 2)$ be a positive integer such that for every $r\geq B(s)$
there exists an infinite set of circulant tournaments $T\in \mathcal{F}%
_{r,s} $. Clearly, $B(2)=2$
and by Proposition \ref{inconn 3}, we have that $B(3)=3$ (see Corollary \ref{r-dic-tensos}).

\begin{proposition}
$B(s)\leq 2B(s-1)-1\leq 2^{s-2}+1$ for every $s\geq 3.$ \label{cota sup}
\end{proposition}

\begin{proof}
We proceed by induction on $s.$ For $s=3,$ by Proposition \ref{inconn 3}, we have
that
\begin{equation*}
B(3)=b(3)=\left\lceil \frac{3}{2}\left\lceil \frac{3}{%
2}\right\rceil \right\rceil =3=2B(2)-1.
\end{equation*}%
Suppose that the statement is valid for some $s\geq 3.$ We will prove it for
$s+1.$ By Proposition \ref{F-123} (i) and (ii), we can construct the
infinite sets
\begin{eqnarray*}
\mathcal{F}_{2r,s+1} &=& \left\{ \overrightarrow{C}_{2r+1}\left\langle \emptyset
\right\rangle \left[ \alpha \right] :\alpha \in \mathcal{F}_{r,s}\right\} \text{ and } \\ 
\mathcal{F}_{2r+1,s+1} &=& \left\{ \overrightarrow{C}%
_{2(3r+1)+1}\left\langle 3r\right\rangle \left[ \alpha \right] :\alpha \in
\mathcal{F}_{r,s}\right\}
\end{eqnarray*}
for every $r\geq B(s)$. It follows that $B(s+1)\leq 2B(s)$. We only need to
prove the existence of an infinite family $\mathcal{F}_{2^{s-2}+1,s}$ for every $s\geq 4$.

Let $s\geq 3$. Notice that $2^{s-2}+1\equiv 0$ (mod $3$) or $2^{s-2}+1\equiv 2$
(mod $3$).

\begin{enumerate}
\item[(i)] If $2^{s-2}+1\equiv 0$ (mod $3$), then $2^{s-2}+1=3q$ for some
integer $q\geq 1$ and by Proposition \ref{F-123}(iii) it follows that $%
\mathcal{F}_{2^{s-2}+1,s}=\left\{ \overrightarrow{C}_{3}\left[ \alpha \right]
:\alpha \in \mathcal{F}_{2q,s-1}\right\} .$

\item[(ii)] If $2^{s-2}+1\equiv 2$(mod $3$), then $2^{s-2}+1=3q+2$ for some
integer $q\geq 1$ and by Proposition \ref{F-123}(iv) it follows that $\mathcal{F}%
_{2^{s-2}+1,s}=\left\{ \overrightarrow{C}_{3}\left[ \alpha \right] :\alpha
\in \mathcal{F}_{2q+1,s-1}\right\} .$
\end{enumerate}
\end{proof}

By Proposition \ref{cota sup} and Proposition \ref{F-123}(iii) and (iv), we
can construct infinite families of circulant tournaments $T$ with arbitrary
\[
\overrightarrow{\omega }_{3}\left( T\right)=s \text{ and }r\geq \left\lceil
\frac{3}{2}b\left( s\right) \right\rceil
\]%
for every $r\geq 2,$ except for the cases when $r\equiv 1$ (mod $3$) and $%
\left\lceil \frac{3}{2}b\left( s\right) \right\rceil \leq r<B\left( s\right)
$. For these values of $r,$ we have to construct each infinite family case
by case. Some of these families are obtained using the construction and the
properties of digraph $D=D_{0}\cup D_{1}\cup D_{2}$ (see Lemmas \ref%
{directed-path} and \ref{directed-path2}). Others are obtained by the
composition $\overrightarrow{C}_{2m+1}\left\langle m-1\right\rangle \left[
\alpha \right] $, where $\alpha $ is an $r$-dichromatic circulant tournament
with $r>m$. Since $r>m,$ these families are not those $\mathcal{F}%
_{2r,s+1}=\{\overrightarrow{C}_{2m+1}\left\langle \emptyset \right\rangle %
\left[ \alpha \right] :\alpha \in \mathcal{F}_{r,s}\}$ given in Proposition %
\ref{F-123}(i). Working with the aforementioned tools, one could obtained
the following infinite sets $\mathcal{F}_{r,s}$ of circulant tournaments:

\begin{enumerate}
\item[(i)] $3\leq s\leq 5$ and every $r\geq b\left( s\right) $,

\item[(ii)] $s=6$ and every $r\geq 12$ and $r\neq 13$,

\item[(iii)] $s=7$ and $r=18,21$ and every $r\geq 25$,

\item[(iv)] $s=8$ and $r=27,32$ and every $r\geq 35$,

\item[(v)] $s=9$ and $r=41,48,51$ and every $r\geq 53$,

\item[(vi)] $s=10$ and $r=62,72,76,77$ and every $r\geq 80$ and

\item[(vii)] $s=11$ and $r=93,108,114,121$ and every $r\geq 123.$
\end{enumerate}

Cases (i) and (ii) are consequences of Proposition \ref{inconn 3}, Theorem %
\ref{cota inf} and using that $b(s)=B(s)$ for $s\in \{2,3,4\}$, $b(6)=12$
and $B(6)=14$. Observe that $\mathcal{F}_{13,6}$ is the first unknown
infinite set.

In Case (iii), we have that $r\geq 18$ by Theorem \ref{cota inf}. By
Proposition \ref{cota sup}, there is an infinite set $\mathcal{F}_{r,7}$ for
every $r\geq 25$. For $r=21,$ let $\alpha \in \mathcal{F}_{14,6}$. Hence $%
dc\left( \overrightarrow{C}_{3}\left[ \alpha \right] \right) =\left\lceil
\frac{14\left( 3\right) }{2}\right\rceil =21$ and $\overrightarrow{\omega }%
_{3}\left( \overrightarrow{C}_{3}\left[ \alpha \right] \right) =2+6-1=7$ by
Corollary \ref{coro-comp} and Proposition \ref{zykov inconn}, respectively.
Therefore, $\mathcal{F}_{21,7}=\left\{ \overrightarrow{C}_{3}\left[ \alpha %
\right] :\alpha \in \mathcal{F}_{14,6}\right\} $. For $r\in
\{19,20,22,23,24\},$ the infinite sets $\mathcal{F}_{r,7}$ are unknown. Let $%
r=25$ and $\alpha \in \mathcal{F}_{12,6}.$ Then $dc\left( \overrightarrow{C}%
_{75}\left\langle 36\right\rangle \left[ \alpha \right] \right) =\left\lceil
\frac{12(75)}{36}\right\rceil =25$ (Corollary \ref{coro-comp} for $m=37$)
and $\overrightarrow{\omega }_{3}\left( \overrightarrow{C}_{75}\left\langle
36\right\rangle \left[ \alpha \right] \right) =2+6-1=7$ (Proposition \ref%
{zykov inconn}). For $r=26,$ take $\alpha \in \mathcal{F}_{17,6}$ and apply
Proposition \ref{F-123}(iv) to obtain $\mathcal{F}_{26,7}=\left\{
\overrightarrow{C}_{3}\left[ \alpha \right] :\alpha \in \mathcal{F}%
_{17,6}\right\} .$ For $r=27,$ take $\alpha \in \mathcal{F}_{18,6}$ and
apply Proposition \ref{F-123}(iii) and we get $\mathcal{F}_{27,7}=\left\{
\overrightarrow{C}_{3}\left[ \alpha \right] :\alpha \in \mathcal{F}%
_{18,6}\right\} .$ Finally, note that $B(7)\leq 2B(6)-1=2\cdot 14-1=27$ (see
Proposition \ref{cota sup}).

Using similar arguments, one can obtain the remaining cases.

The following table summarizes some exact values of $b(s)$ and $B(s).$

\[
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$s$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ \\ \hline
$b(s)$ & $2$ & $3$ & $5$ & $8$ & $12$ & $18$ & $27$ & $41$ & $62$ & $93$ \\
\hline
$B(s)$ & $2$ & $3$ & $5$ & $9$ & $14$ & $25$ & $35$ & $53$ & $80$ & $123$ \\
\hline
\end{tabular}%
\]

We finish with the following conjecture.

\begin{conjecture}
$B(s)\leq 2b(s-1)-1$ for every $s\geq 3.$
\end{conjecture}

\noindent \textbf{Acknowledgment.} We thank the anonymous referees for their
suggestions that helped us to significantly improve the presentation of this
paper.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection*{Acknowledgements}
%Thanks to Professor Querty for suggesting the proof of
%Lemma~\ref{lem:Technical}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{familia} G. Araujo-Pardo and M. Olsen. \newblock A conjecture of
Neumann-Lara on infinite families of $r$-dichromatic circulant tournaments.
\newblock {\em Discrete Math.}, 310:489--492, 2010.

\bibitem{torneos} J. Bang-Jensen and G. Gutin. \newblock {\em Digraphs. Theory, algorithms and applications} (2nd ed.).
\newblock Springer Monographs in Mathematics. Springer-Verlag London, Ltd. London, 2009.

\bibitem{Bondy} J.~A. Bondy and U.~S.~R. Murty. \newblock {\em Graph Theory}. \newblock Graduate Texts in Mathematics, no. 244. Springer, New York, 2008.

\bibitem{Erdos} Paul Erd\H{o}s. \newblock Problems and results in number theory and graph theory. \newblock In {\em Proceedings of the
Ninth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba,
Winnipeg, Man., 1979)}. \newblock Congress. Numer., XXVII, pages 3--21. Utilitas Math., Winnipeg,
Man., 1979.

\bibitem{GN} H. Galeana-S\'{a}nchez and V. Neumann-Lara. \newblock A class of
tight circulant tournaments. \newblock {\em Discuss. Math. Graph Theory}
20:109--128, 2000.

\bibitem{simple} B. Llano. \newblock Two characterizations of simple circulant tournaments. \newblock \arxiv{1507.03623}, 2015.

\bibitem{agudo} B. Llano and V. Neumann-Lara. \newblock Circulant tournaments
of prime order are tight. \newblock {\em Discrete Math.}, 308:6056--6063, 2008.

\bibitem{fam-inf} B. Llano and M. Olsen. \newblock Infinite families of tight
regular tournaments. \newblock {\em Discuss. Math. Graph Theory}, 27:299--311, 2007.

\bibitem{lagos} B. Llano and M. Olsen. \newblock On a conjecture of V\'{\i}ctor Neumann-Lara.
\newblock (The IV Latin-American Algorithms, Graphs, and
Optimization Symposium.) \newblock {\em Electron. Notes Discrete Math.}, 30:207--212, 2008.

\bibitem{NS} J. Ne\v{s}et\v{r}il and E. Sopena. \newblock On the Oriented Game
Chromatic Number. \newblock {\em Electron. J. Combin.}, 8(2), Research Paper 14, 2001.

\bibitem{gendc} V. Neumann-Lara. \newblock The generalized dichromatic number
of a digraph. \newblock In {\em Finite and infinite sets, Vol. I, II (Eger, 1981)}, volume 37 of
{\em Colloq. Math. Soc. J\'{a}nos Bolyai}, pages 601--606. North-Holland, Amsterdam,
1984.

\bibitem{dc} V. Neumann-Lara. \newblock The dichromatic number of a digraph.
\newblock {\em J. Combin. Theory Ser. B}, 33:265--270, 1982.

\bibitem{inconn} V. Neumann-Lara. \newblock The acyclic disconnection of a
digraph. \newblock {\em Discrete Math.}, 197/198:617--632, 1999.

\bibitem{zykov} V. Neumann-Lara. \newblock Dichromatic number, circulant
tournaments and Zykov sums of digraphs. \newblock {\em Discuss. Math. Graph Theory},
20:197--207, 2000.

\bibitem{NLU} V.Neumann-Lara and J. Urrutia. \newblock Vertex critical $r$-dichromatic tournaments.
\newblock {\em Discrete Math.}, 49:83--87, 1984.

\bibitem{Cota} A.~M. Odlyzko and H.~S. Wilf. \newblock Functional iteration
and the Josephus problem. \newblock {\em Glasgow Math. J.}, 33(2):235-240, 1991.

\bibitem{Reid} K.~B. Reid, \newblock Tournaments. \newblock In {\em Handbook of Graph Theory. Jonathan Gross, Jay
Yellen (Eds.)}, pages 156--184. CRC Press, 2004.

\bibitem{YZ} D. Yang and X. Zhu, \newblock Game colouring directed graphs.
\newblock {\em Electron. J. Combin.}, 17(1), Research Paper 11, 2010.

\end{thebibliography}

\end{document}
