# Bipartitions with prescribed order of highly connected digraphs111The
author’s work is supported by National Natural Science Foundation of China,
Grant/Award Number: 12071260.

Yuzhen Qi, Jin Yan222Corresponding author. E-mail address<EMAIL_ADDRESS>Jia Zhou
School of Mathematics, Shandong University, Jinan 250100, China

Abstract: A digraph is strongly connected if it has a directed path from $x$
to $y$ for every ordered pair of distinct vertices $x,y$ and it is strongly
$k$-connected if it has at least $k+1$ vertices and remains strongly connected
when we delete any set of at most $k-1$ vertices. For a digraph $D$, we use
$\delta(D)$ to denote $\mathop{\text{min}}\limits_{v\in
V(D)}{|N_{D}^{+}(v)\cup N_{D}^{-}(v)|}$. In this paper, we show the following
result. Let $k,l,n,n_{1},n_{2}\in\mathbb{N}$ with $n_{1}+n_{2}\leq n$ and
$n_{1},n_{2}\geq n/20$. Suppose that $D$ is a strongly
$10^{7}k(k+l)^{2}\log(2kl$)-connected digraph of order $n$ with $\delta(D)\geq
n-l$. Then there exist two disjoint subsets $V_{1},V_{2}\in V(D)$ with
$|V_{1}|=n_{1}$ and $|V_{2}|=n_{2}$ such that each of $D[V_{1}]$, $D[V_{2}]$,
and $D[V_{1},V_{2}]$ is strongly $k$-connected. In particular, $V_{1}$ and
$V_{2}$ form a partition of $V(D)$ when $n_{1}+n_{2}=n$. This result improves
the earlier result of Kim, Kühn, and Osthus [SIAM J. Discrete Math. 30 (2016)
895–911].

Keywords: digraph, connectivity, partition

AMS subject classifications. 05C20, 05C40

##  1 Introduction

Given a digraph $D$, we write $D[U]$ for the subgraph of $D$ induced by a
vertex set $U$ of $D$, and for two disjoint vertex sets $A,B$ of $D$, we use
$D[A,B]$ to denote the subgraph of $D$, which consists of all arcs between $A$
and $B$ in $D$ but no others and $V(D[A,B])=A\cup B$. A digraph is _strongly
connected_ if it has a directed path from $x$ to $y$ for every ordered pair of
distinct vertices $x,y$ and it is $strongly$ $k$-$connected$ if it has at
least $k+1$ vertices and remains strongly connected when we delete any set of
at most $k-1$ vertices.

Recently, researchers have shown an increased interest in the partitions of
(di)graphs into subgraphs which inherit some properties of the original
(di)graph. Thomassen [11] asked whether for integers $k_{1},\ldots,k_{t}$,
there exists $f(k_{1},\ldots,k_{t})$ such that every strongly
$f(k_{1},\ldots,k_{t})$-connected tournament $T$ admits a vertex-partition
$W_{1},\ldots,W_{t}$ such that $T[W_{i}]$ is a strongly $k_{i}$-connected
subtournament for each $i\in[t]$?

Kühn, Osthus and Townsend [8] answered the above problem by showing that every
strongly $10^{7}k^{6}t^{3}$log$(kt^{2})$-connected tournament $T$ admits a
vertex-partition $V_{1},\ldots,V_{t}$ such that $T[V_{i}]$ is a strongly
$k$-connected subtournament for each $i\in[t]$. In 2020, Kang and Kim [5]
improved this result in the following theorem. Here,
$\delta(D)=\mathop{\text{min}}\limits_{v\in V(D)}{|N_{D}^{+}(v)\cup
N_{D}^{-}(v)|}$ and $\log k=\log_{2}k$ for $k\in\mathbb{N}$.

###### Theorem 1.1

[5] Let $k,t,l,m,n,q,a_{1},\ldots,a_{t}\in\mathbb{N}$ with $t,m\geq 2$,
$\sum_{i\in[t]}a_{i}\leq n$ and $a_{i}\geq n/(10tm)$ for each $i\in[t]$.
Suppose that D is a strongly $10^{8}qk^{2}l(k+l)^{2}tm^{2}\log(m)$-connected
digraph of order n with $\delta(D)\geq n-l$, and $Q_{1},\ldots,Q_{t}\subseteq
V(D)$ are t disjoint sets with $|Q_{i}|\leq q$ for each $i\in[t]$. Then there
exist disjoint sets $W_{1},\ldots,W_{t}$ of $V(D)$ satisfying the following.

(1) $Q_{i}\subseteq W_{i}$.

(2) For every $i\in[t]$, the subgraph $D[W_{i}]$ is strongly $k$-connected.

(3) $|W_{i}|=a_{i}$.

Recently, Girão and Letzter [3] showed that there exists a constant $c>0$ such
that the vertices of every strongly $c\cdot kt$-connected tournament can be
partitioned into $t$ parts, each of which induces a strongly $k$-connected
tournament.

On the other hand, Kim, Kühn and Osthus [6] proved that an even stronger type
of bipartition can be obtained.

###### Theorem 1.2

[6] Let $k\in\mathbb{N}$, and let T be a strongly
$10^{9}k^{6}\log(2k)$-connected tournament. Then there exists a partition
$V_{1}$, $V_{2}$ of $V(T)$ such that each of $T[V_{1}]$, $T[V_{2}]$, and
$T[V_{1},V_{2}]$ is strongly $k$-connected.

Inspired by Theorems 1.1 and 1.2, we prove the following result.

###### Theorem 1.3

Let $k,l,n,n_{1},n_{2}\in\mathbb{N}$ with $n_{1}+n_{2}\leq n$ and
$n_{1},n_{2}\geq n/20$. Suppose that D is a strongly
$10^{7}k(k+l)^{2}\log(2kl)$-connected digraph of order n with $\delta(D)\geq
n-l$. Then there exist two disjoint subsets $V_{1},V_{2}$ of $V(D)$ satisfying
the following.

(1) $|V_{i}|=n_{i}$ for each $i\in[2]$.

(2) Each of $D[V_{1}]$, $D[V_{2}]$, and $D[V_{1},V_{2}]$ is strongly
$k$-connected.

In particular, $V_{1}$ and $V_{2}$ form a partition of $V(D)$ when
$n_{1}+n_{2}=n$.

Camion Theorem [2] states that every strongly connected tournament contains a
Hamiltonian cycle. In 1966, Moon [10] extended this result by showing that for
any strongly connected tournament $T$ and a vertex $v\in V(T)$, there exists a
cycle $C$ of length $3\leq|C|\leq|T|$ such that $v\in V(C)$. Moreover, we
prove the following result.

###### Corollary 1.1

Let $n,t\in\mathbb{N}$ with $n\geq 6$ and $3\leq t\leq n-3$, and let $T$ be a
strongly $4\cdot 10^{7}$-connected tournament of order n with a vertex $v\in
V(T)$. Then there exist two disjoint cycles $C_{1}$ and $C_{2}$ in $T$ such
that $v\in V(C_{1})$, $|C_{1}|=t$ and $|C_{2}|=n-t$.

######  Proof.

By Theorem 1.3, there exists a partition $V_{1}$, $V_{2}$ of $V(T)$ such that
each of $T[V_{1}]$, $T[V_{2}]$, and $T[V_{1},V_{2}]$ is strongly connected.
One may assume $v\in V_{1}$. If $|V_{1}|\geq t$, then by Moon Theorem,
$T[V_{1}]$ has a cycle $C_{1}$ of length $t$ and $v\in V(C_{1})$. Because
$T[V_{1},V_{2}]$ is strongly connected, each vertex $u\in V_{1}\setminus
V(C_{1})$ has an in-neighbor and an out-neighbor in $V_{2}$. So,
$V(T)\setminus V(C_{1})$ is strong. Owing to Camion Theorem, we are done.
Otherwise, Moon Theorem shows that $T[V_{2}]$ has a cycle $C_{2}$ of length
$n-t$. Similarly, $V(T)\setminus V(C_{2})$ is strong, and then
$T[V(T)\setminus V(C_{2})]$ has a Hamiltonian cycle.

Partitioning an undirected graph into several parts under connectivity
constraint has been widely studied due to its important applications. A number
of classical results in undirected graphs have been achieved. Surveys such as
that conducted by Hajnal [4] and Thomassen [12] proved that for every $k$
there exists an integer $f(k)$ such that every $f(k)$-connected graph has a
vertex partition into sets $A$ and $B$ so that both $A$ and $B$ induce
$k$-connected graphs. Later, Kühn and Osthus [7] further strengthened this by
requiring that each vertex in $A$ has many neighbours in $B$.

The rest of the paper is organized as follows. Section 2 contains
preliminaries and tools throughout the paper. The proof of Theorem 1.3 is
given in Section 3, which consists of 4 subsections.

##  2 Preliminaries and tools

###  2.1 Basic terminology

Given $k\in\mathbb{N}$, let $[k]=\\{1,\ldots,k\\}$ and
$[k,k+l]=\\{k,\ldots,k+l\\}$. The digraphs considered in this paper are always
simple (without loops and multiple arcs). Let $D$ be a digraph with vertex set
$V(D)$ and arc set $A(D)$. We write $|D|$ for the number of vertices in $D$
and $xy$ for an arc directed from $x$ to $y$. Moreover, we call $x$ _in-
neighbor_ of $y$ and $y$ _out-neighbor_ of $x$ or $x$ dominates $y$ and $y$ is
dominated by $x$. For any vertex $x\in V(D)$, let $N^{+}_{D}(x)=\\{y:xy\in
A(D)\\}$ and $N^{-}_{D}(x)=\\{y:yx\in A(D)\\}$ be the _out-neighborhood_ and
the _in-neighborhood_ of $x$, respectively. Similarly, define
$N^{-!}_{D}(x)=\\{y:yx\in A(D)\text{ and }xy\notin A(D)\\}$ and
$N^{+!}_{D}(x)=\\{y:xy\in A(D)\text{ and }yx\notin A(D)\\}$. We call
$d_{D}^{+}(x)=|N_{D}^{+}(x)|$, $d_{D}^{-}(x)=|N_{D}^{-}(x)|$,
$d^{-!}_{D}(x)=|N^{-!}_{D}(x)|$ and $d^{+!}_{D}(x)=|N^{+!}_{D}(x)|$ the _out-
degree_ , the _in-degree_ , the _sole in-degree_ and the _sole out-degree_ of
$x$ in $D$, respectively. Further, let $\delta^{-}(D)$ and $\delta^{+}(D)$
denote the _minimum in-degree_ and the _minimum out-degree_ of $D$.

Given a digraph $D$ and a path $P=v_{1}v_{2}\cdots v_{l}$ of $D$, we use
$v_{i}Pv_{j}$ to denote the subpath of $P$ from $v_{i}$ to $v_{j}$, and denote
the set $V(P)\setminus\\{v_{1},v_{l}\\}$ of internal vertices of $P$ by
$\text{Int}(P)$. The _length_ of $P$ is the number of its vertices. A path $P$
is called $odd$ if its length is odd, and $even$ if its length is even.

Let $A$ and $B$ be two subsets of $V(D)$. We say that $A$ _in-dominates_
(resp. _out-dominates_) $B$ if for every vertex $b\in B$ there exists a vertex
$a\in A$ such that $ba\in A(D)$ (resp. $ab\in A(D)$). Further, we call $A$ an
_almost in-dominating set_ (resp. _almost out-dominating set_) if there exists
a vertex subset $E$ of $V(D)$ such that $A$ in-dominates (resp. out-dominates)
$V(D)\setminus(A\cup E)$. In particular, if $E=\emptyset$, then we call $A$ an
_in-dominating set_ (resp. _out-dominating set_). For a vertex set $U$ and a
vertex $v$ in $D$, we say that $(v,U)$ is $k$_-connected_ in $D$ if for any
subset $S\subseteq V(D)\setminus\\{v\\}$ with $|S|\leq k-1$, there exists a
path from $v$ to a vertex in $U\setminus S$ in $D\setminus S$. Similarly, we
say $(U,v)$ is $k$_-connected_ in $D$ if for any subset $S\subseteq
V(D)\setminus\\{v\\}$ with $|S|\leq k-1$, there exists a path from a vertex in
$U\setminus S$ to $v$ in $D\setminus S$. Note that $U$ does not have to be a
subset of $V(D)$ in this definition. However, if $(v,U)$ is $k$-connected in
$D$ or $(U,v)$ is $k$-connected in $D$, then either $v\in U$ or $|U\cap
V(D)|\geq k$.

###  2.2 Some lemmas

We now collect some results that will be used frequently in the whole paper.
The following two lemmas guarantee the existence of a suitable almost
dominating set in a digraph close to being semicomplete. A tournament $T$ of
order $n$ is _transitive_ if there exists an ordering $v_{1},\ldots,v_{n}$ of
its vertices such that $v_{i}v_{j}\in A(T)$ if and only if $i<j$. In this
case, we often say that $v_{1}$ is the _tail_ of $T$ and $v_{n}$ is the _head_
of $T$.

###### Lemma 2.1

Let $n,l,c\in\mathbb{N}$ with $c\geq 2$ and let $D$ be a digraph with
$\delta(D)\geq n-l$. For any vertex $v\in V(D)$ with $d_{D}^{-}(v)\geq
2^{c-1}l$, there exist disjoint sets $A,E\subseteq V(D)$ and a vertex $a\in A$
such that the following properties hold:

(i) $2\leq|A|\leq c$, and $D[A]$ has a spanning transitive tournament with
tail $a$ and head $v$.

(ii) $A\setminus\\{a\\}$ out-dominates $V(D)\setminus(A\cup E)$.

(iii) $|E|\leq(1/2)^{c-2}d^{-}_{D}(v)+c(l-1)$.

######  Proof.

Let $v_{1}:=v$. To this end, we will find $A$ by choosing vertices
$v_{1},\ldots,v_{i}$ such that
$v_{i}\in\bigcap\limits_{j\in[i-1]}N^{-}(v_{j})$, and the order of union of
the out-neighborhood of $v_{j}$ is as large as possible at each step. More
precisely, suppose inductively that for some $1\leq i<c$ we have already found
a set $A_{i}=\\{v_{1},\ldots,v_{i}\\}$ and a set $E_{i}$ such that the
following hold:

(a) $D[A_{i}]$ has a spanning transitive tournament with tail $v_{i}$ and head
$v_{1}$;

(b) $A_{i}$ out-dominates $V(D)\setminus(A_{i}\cup E_{i})$, where
$E_{i}=V(D)\setminus\bigcup\limits_{j\in[i]}N^{+}(v_{i})$;

(c) $|E_{i}|\leq(1/2)^{i-1}d^{-}_{D}(v)+(i+1)(l-1)$.

Note that $A_{1}$ satisfies (a)-(c), since $E_{1}=N_{D}^{-}(v_{1})$ and
$|E_{1}|\leq d^{-}_{D}(v_{1})+2(l-1)$. Set
$U_{i}=\bigcap\limits_{j\in[i]}N^{-}(v_{j})$. We will either find desired sets
$A$ and $E$, or extend $A_{i}$ by adding a new vertex in $U_{i}$. We see that
if $|E_{i}|\leq(1/2)^{c-2}d^{-}_{D}(v)+c(l-1)$, then choose $a\in U_{i}$. Let
$A:=A_{i}\cup\\{a\\}$ and $E:=E_{i}\setminus\\{a\\}$, as required. Hence
$|E_{i}|>(1/2)^{c-2}d^{-}_{D}(v)+c(l-1)$. It follows from the definition of
$U_{i}$ that $|U_{i}|>2l$. Let $U_{i}^{\prime}$ be a subset of $U_{i}$ such
that the in-degree of each vertex in $U_{i}^{\prime}$ is at least one.
Obviously, $|U_{i}^{\prime}|\geq l$ and $U_{i}^{\prime}$ has a vertex $u$ of
sole in-degree at most $|U_{i}^{\prime}|/2$ in $D[U_{i}^{\prime}]$. Choose
$v_{i+1}:=u$. Therefore,

$|E_{i+1}|=|V(D)\setminus\bigcup\limits_{j\in[i+1]}N^{+}(v_{j})|\leq(1/2)^{i}d^{-}_{D}(v)+(i+2)(l-1).$

By repeating this construction, we will eventually gain
$|E_{i}|\leq(1/2)^{c-2}d^{-}_{D}(v)+c(l-1)$ for some $i\leq c-1$. Then choose
$a\in U_{i}$. Let $A:=A_{i}\cup\\{a\\}$ and $E:=E_{i}\setminus\\{a\\}$. This
completes the proof of Lemma 2.1.

The next lemma follows immediately from Lemma 2.1 by reversing the
orientations of all arcs.

###### Lemma 2.2

Let $n,l,c\in\mathbb{N}$ with $c\geq 2$ and let $D$ be a digraph with
$\delta(D)\geq n-l$. For any vertex $v\in V(D)$ with $d_{D}^{+}(v)\geq
2^{c-1}l$, there exist disjoint sets $B,E\subseteq V(D)$ and a vertex $b\in B$
such that the following properties hold:

(i) $2\leq|B|\leq c$, and $D[B]$ has a spanning transitive tournament with
tail $v$ and head $b$;

(ii) $B\setminus\\{b\\}$ in-dominates $V(D)\setminus(B\cup E)$;

(iii) $|E|\leq(1/2)^{c-2}d^{+}_{D}(v)+c(l-1)$.

A digraph $D$ is $k$_-linked_ if $|D|\geq 2k$ and, whenever
$(x_{1},y_{1}),\ldots,(x_{k},y_{k})$ are ordered pairs of (not necessarily
distinct) vertices of $D$, there exist distinct internally disjoint paths
$P_{1},\ldots,P_{k}$ such that for all $i\in[k]$ we have that $P_{i}$ is a
path from $x_{i}$ to $y_{i}$ and that
$\\{x_{1},\ldots,x_{k},y_{1},\ldots,y_{k}\\}\cap V(P_{i})=\\{x_{i},y_{i}\\}$.
The following proposition follows immediately from the definition of
linkedness and the pigeonhole principle.

###### Proposition 2.1

Let $k,s\in\mathbb{N}$, and let $D$ be a $ks$-linked digraph. Let
$(x_{1},y_{1}),\ldots,(x_{k},y_{k})$ be ordered pairs of (not necessarily
distinct) vertices of $D$. Then the following two statements hold.

(i) $D$ contains $ks$ distinct internally disjoint paths
$P^{1}_{1},\ldots,P_{k}^{s}$ such that for all $i\in[k]$ and $j\in[s]$ we have
that $P_{i}^{j}$ is a directed path from $x_{i}$ to $y_{i}$ and that
$\\{x_{1},\ldots,x_{k},y_{1},\ldots,y_{k}\\}\cap
V(P_{i}^{j})=\\{x_{i},y_{i}\\}$.

(ii) There exist $s^{\prime}\leq s$ internally disjoint paths such that the
length of these paths is at most $(s^{\prime}|D|)/s$.

It is easy to see that every $k$-linked digraph is strongly $k$-connected. The
converse is not true. Meng, Rolek, Wang and Yu [9] proved that every strongly
$(40k-31)$-connected tournament is $k$-linked. Later, Bang-Jensen and Johansen
[1] improved their result by showing that every strongly $(13k-6)$-connected
tournament with minimum out-degree at least $28k-13$ is $k$-linked. Recently,
Zhou, Qi and Yan [13] extended the result to a digraph by proving the
following theorem.

###### Theorem 2.1

[13] For each $n,k,l\in\mathbb{N}$, every strongly $(50k+20l)$-connected
digraph with $\delta(D)\geq n-l$ is $k$-linked.

Lemma 2.3 states that there exist small (not necessarily disjoint) vertex sets
$U$ and $W$ in a digraph such that every vertex in a digraph can reach $U$ and
can be reached by a vertex in $W$. Moreover, Proposition 2.2 guarantees that a
digraph has a small vertex set $U$ such that every vertex outside $U$ has many
out- and in-neighbors in $U$.

###### Lemma 2.3

[5] Let $n,k,l\in\mathbb{N}$ and let $D$ be a digraph of order $n$ with
$\delta(D)\geq n-l$. Then there exist two sets $U,W\subseteq V(D)$ satisfying
the following.

(i) $|U|,|W|\leq 2k+l-2$.

(ii) For every $v\in V(D)$, both $(v,U)$ and $(W,v)$ are $k$-connected in $D$.

###### Proposition 2.2

Let $n,k,l\in\mathbb{N}$ and let $D$ be a digraph of order $n$ with
$\delta(D)\geq n-l$. Then there is a set $U\subseteq V(D)$ with $|U|\leq
3(k+l)\log n$ such that each vertex in $V(D)\setminus U$ has at least $k$ out-
neighbors and at least $k$ in-neighbors in $U$.

######  Proof.

First, we construct an almost in-dominating set $V_{1}$ of order at most
$c=\lceil\log n\rceil\leq(3\log n)/2$. Roughly speaking, we will find $V_{1}$
by choosing vertices $v_{1},\ldots,v_{i}$ such that
$v_{i}\in\bigcap\limits_{j\in[i-1]}N_{D}^{+!}(v_{j})$ with minimum sole out-
degree in $\bigcap\limits_{j\in[i-1]}N_{D}^{+!}(v_{j})$ at each step for
$i\in[c]$. We first choose $v_{1}\in V(D)$ with minimum sole out-degree in
$D$. Set $A_{1}:=\\{v_{1}\\}$ and $E_{1}:=N^{+!}_{D}(v_{1})$. Obviously,
$A_{1}$ is an almost in-dominating set. Hence $|E_{1}|\leq\lceil n/2\rceil$.
Then we choose vertices $v_{2},\ldots,v_{i}$ such that the sole out-degree of
$v_{i}$ in $E_{i-1}$ is minimum at each step. Set
$A_{i}:=A_{i-1}\cup\\{v_{i}\\}$ and $E_{i}:=E_{i-1}\cap N^{+!}_{D}(v_{j})$.
Then $A_{i}$ is an almost in-dominating set. This yields $|E_{i}|\leq\lceil
n/2^{i-1}\rceil$. Let $r$ be an integer such that $2^{r}\leq n<2^{r+1}$. Note
that if $i$ is larger than $r+1$, then $E_{i}$ is empty and it not hard to see
$r+1\geq\lceil\log n\rceil$. Therefore, let $V_{1}=A_{r+1}$ be the desired
almost in-dominating set.

We now apply this argument again, with $V(D)$ replaced by
$V(D)\setminus(V_{1}\cup\cdots\cup V_{j})$ with $j\in[k+l-1]$, to obtain $k+l$
disjoint almost in-dominating sets $V_{1},\ldots,V_{k+l}$ with $|V_{i}|\leq c$
for all $i\in[k+l]$. Proceed similarly to obtain disjoint almost out-
dominating sets $V_{1}^{\prime},\ldots,V_{k+l}^{\prime}$ with
$|V_{i}^{\prime}|\leq c$ for all $i\in[k+l]$ in $D-\bigcup_{i\in[k+l]}V_{i}$.
Take $U:=V_{1}\cup\cdots\cup V_{k+l}\cup V_{1}^{\prime}\cup\cdots\cup
V_{k+l}^{\prime}$ as required.

##  3 Proof of Theorem 1.3

Outline of the proof. The idea of the proof of Theorem 1.3 goes back at least
as far as [6]. Our proof involves looking at constructing small disjoint out-
dominating sets $A_{i}\setminus\\{a_{i}\\}$, where $i\in[6k]$, such that each
$D[A_{i}]$ has a spanning transitive tournament with head $x_{i}$ and tail
$a_{i}$. Similarly, we also need to construct small disjoint in-dominating
sets $B_{i}\setminus\\{b_{i}\\}$, where $i\in[6k]$, so that each $D[B_{i}]$
has a spanning transitive tournament with head $b_{i}$ and tail $y_{i}$.
Because $D$ is highly connected, provided that all these dominating sets are
small enough, then we can use Proposition 2.1 (i) to find $6k$ disjoint paths
$P_{i}$ joining the head $b_{i}$ of $B_{i}$ to the tail $a_{i}$ of $A_{i}$.

We see that if

$\displaystyle\bigcup\limits_{i\in[k]}(A_{i}\cup B_{i}\cup
V(P_{i}))\cup\\{a_{2k+1},b_{2k+1},b_{4k+1},a_{5k+1}\\}\subseteq
V_{1},\bigcup\limits_{i\in[k+1,2k]}(A_{i}\cup B_{i}\cup V(P_{i}))$ (1)
$\displaystyle\cup\\{a_{3k+1},b_{3k+1},a_{4k+1},b_{5k+1}\\}\subseteq
V_{2}\text{ and }\bigcup\limits_{i\in[2k+1,6k]}(A_{i}\cup B_{i}\cup
V(P_{i}))\subseteq D[V_{1},V_{2}],$

then for any set $S$ with $|S|\leq k-1$, we can choose an index $i\in[6k]$
such that $(A_{i}\cup B_{i}\cup V(P_{i}))\cap S=\emptyset$. This implies that
if $x,y\in V_{1}\setminus S$, then we can find a path from $x$ to $y$ in
$D[V_{1}\setminus S]$ by utilizing $P_{i}$. Hence $D[V_{1}]$ is strongly
$k$-connected. In the same way, both $D[V_{2}]$ and $D[V_{1},V_{2}]$ are
strongly $k$-connected.

However, we cannot hope for this ideal case, due to several issues. The
following are some major issues complicating the proof.

$\bullet$ As out- or in-dominating sets may be large in general, we can not
use Proposition 2.1 (i) to get paths $P_{1},\ldots,P_{6k}$. Hence we will use
Lemmas 2.1 and 2.2 to construct small “almost out-dominating sets” $A_{i}$ and
“almost in-dominating sets” $B_{i}$ in Subsection 3.1. This means that there
is a small “exceptional set” of vertices that are not out-dominated (resp. in-
dominated) by $A_{i}$ (resp. $B_{i}$). That is, a vertex in an “exceptional
set” can not receive an arc from $A_{i}$ or send an arc to $B_{i}$. Instead of
receiving/sending an arc from $A_{i}$/to $B_{i}$ , we will use the notion of
“safe” vertices (see Definition 3.1) to find a path from $A_{i}$ to a vertex
in an “exceptional set” or from a vertex in an “exceptional set” to $B_{i}$.

$\bullet$ Owing to (1), we obtain $P_{2k+1}\cup\cdots\cup P_{6k+1}\subseteq
D[V_{1},V_{2}]$. This implies that the length of $P_{i}$ is odd if $a_{i}$ and
$b_{i}$ belong to the same partite. Otherwise, the length of $P_{i}$ is even.
Hence we will use the notion of “correct” path (see Definition 3.2) to make
sure that the length of this path is even or odd.

In the proof of Theorem 1.3, we will construct the sets $V_{1},V_{2}$ in
several steps by coloring the vertices of $V(D)$ with colors $I$ and $II$. At
each step and for $i\in\\{I,II\\}$, let $V_{i}=\\{v\in V(D):v\text{ is colored
by }i\\}$, and meanwhile we guarantee the safety of all colored vertices at
this step. Finally, let $V_{1}:=V_{I}$ and $V_{2}:=V_{II}$. The construction
and coloring mainly consist of four steps:

$(a)$ Constructing $6k$ almost out-dominating sets $A_{1},\ldots,A_{6k}$ and
$6k$ almost in-dominating sets $B_{1},\ldots,B_{6k}$ satisfy (P0)-(P4). Then
we can color all vertices in $A_{1}\cup\cdots\cup A_{6k}\cup B_{1}\cdots\cup
B_{6k}$ and some other vertices such that all colored vertices are safe (see
Claim 3.2). Let $C_{1}$ be a set consisting of all vertices colored so far.

$(b)$ Finding correct $i$-paths for each $i\in[6k]$, coloring all vertices in
correct $i$-paths and some other vertices such that all colored vertices are
safe (see Claims 3.3-3.9). Let $C_{5}$ be the set consisting of all vertices
colored so far. So $C_{1}\subseteq C_{5}$.

$(c)$ Coloring all remaining vertices such that all vertices are safe (see
Claim 3.11). Let $C_{6}$ be the set consisting of all vertices colored so far.
So $C_{5}\subseteq C_{6}$.

$(d)$ Constructing $V_{1}$ and $V_{2}$ (see Claim 3.12).

###  3.1 Construction of almost dominating sets

Let $D$ be a strongly $10^{7}k(k+l)^{2}\log(2kl)$-connected digraph of order
$n$ with $\delta(D)\geq n-l$. Let $X=\\{x_{1},x_{2},\ldots,x_{6k}\\}$ be a set
of $6k$ vertices with smallest in-degrees in $D$, and
$Y=\\{y_{1},y_{2},\ldots,y_{6k}\\}$ be a set of $6k$ vertices with smallest
out-degrees in $V(D)\setminus X$. Define

$\hat{\delta}^{-}(D)=\mathop{\text{min}}\limits_{v\in V(D)\setminus
X}d_{D}^{-}(v)\ \ \ \ \text{ and }\ \ \ \
\hat{\delta}^{+}(D)=\mathop{\text{min}}\limits_{v\in V(D)\setminus
Y}d_{D}^{+}(v).$

Since $D$ is strongly $10^{7}k(k+l)^{2}\log(2kl)$-connected, it follows that

$\text{min}\\{n,\hat{\delta}^{-}(D),\hat{\delta}^{+}(D)\\}\geq
10^{7}k(k+l)^{2}\log(2kl).$ (2)

Let $c=\lceil\text{log}(18000k^{2})\rceil+2\leq 20k$. We first repeatedly
apply Lemma 2.1 (removing the dominating sets obtained already each time) with
parameter $c$ and a vertex in $X$ to obtain almost out-dominating sets
$A_{1},\ldots,A_{6k}$ and sets of vertices $E_{A_{1}},\ldots,E_{A_{6k}}$.
Proceed similarly (apply Lemma 2.2 with parameter $c$ and a vertex in $Y$ by
removing the dominating sets each time) to obtain disjoint almost in-
dominating sets $B_{1},\ldots,B_{6k}$, and sets of vertices
$E_{B_{1}},\ldots,E_{B_{6k}}$. Write $D_{0}=\bigcup_{i\in[6k]}(A_{i}\cup
B_{i})$. We have the following statements.

(P0) The sets $A_{1},\ldots,A_{6k},B_{1},\ldots,B_{6k}$ are pairwise disjoint.
Moreover, $2\leq|A_{i}|,|B_{i}|\leq c$.

(P1) $D[A_{i}]$ has a spanning transitive tournament with head $x_{i}$ and
tail $a_{i}$, and $D[B_{i}]$ has a spanning transitive tournament with tail
$y_{i}$ and head $b_{i}$.

(P3) $A_{i}\setminus\\{a_{i}\\}$ out-dominates $V(D)\setminus(D_{0}\cup
E_{A_{i}})$, and $B_{i}\setminus\\{b_{i}\\}$ in-dominates
$V(D)\setminus(D_{0}\cup E_{B_{i}})$.

(P4) $|E_{A_{i}}|\leq(1/2)^{c-2}\hat{\delta}^{-}(D)+(c-1)(l-1)$ and
$|E_{B_{i}}|\leq(1/2)^{c-2}\hat{\delta}^{+}(D)+(c-1)(l-1)$.

By symmetry, assume $\hat{\delta}^{+}(D)\geq\hat{\delta}^{-}(D)$. Let
$E_{A}=\bigcup_{i\in[6k]}E_{A_{i}}$, $E_{B}=\bigcup_{i\in[6k]}E_{B_{i}}$ and
$E=E_{A}\cup E_{B}$. It follows from (1) and (P4) that

$\displaystyle|E_{A}|$ $\displaystyle\leq
6k\cdot(\frac{\hat{\delta}^{-}(D)}{18000k^{2}}+20kl)\leq\frac{\hat{\delta}^{-}(D)}{3\cdot
10^{3}k}+120k^{2}l\leq\frac{\hat{\delta}^{-}(D)}{2\cdot 10^{3}k},$ (3)
$\displaystyle|E_{B}|\leq\frac{\hat{\delta}^{+}(D)}{2\cdot 10^{3}k}\text{ and
}|E|\leq|E_{A}|+|E_{B}|\leq\frac{\hat{\delta}^{+}(D)}{1000k}.$

Next we will construct the sets $V_{1},V_{2}$ in several steps. We will color
the vertices of $V(D)$ with colors $I$ and $II$. At each step, we use $V_{I}$
and $V_{II}$ to denote the set of vertices of colors $I$ and $II$,
respectively. We start with no vertices of $D$ colored, and we now begin to
color all vertices in $D_{0}$. In what follows, let the vertices in

$\displaystyle D_{0}^{\prime}=$
$\displaystyle\bigcup\limits_{i\in[k]}(A_{i}\cup
B_{i})\cup\bigcup\limits_{i\in[2k+1,3k]}\\{a_{i},b_{i}\\}\cup\bigcup\limits_{i\in[3k+1,4k]}(A_{i}\cup
B_{i}\setminus\\{a_{i},b_{i}\\})$
$\displaystyle\cup\bigcup\limits_{i\in[4k+1,5k]}(A_{i}\cup\\{b_{i}\\}\setminus\\{a_{i}\\})\cup\bigcup\limits_{i\in[5k+1,6k]}(B_{i}\cup\\{a_{i}\\}\setminus\\{b_{i}\\})$

be colored with $I$ and all vertices in $D_{0}\setminus D_{0}^{\prime}$ be
colored with $II$ (see Fig. 1).

Fig. 1:  Color all vertices in $D_{0}$ in the case when $k=1$.

To solve the problem discussed earlier we will introduce the notion of “safe”
vertices.

###### Definition 3.1

(Safe vertex) For each $i\in\\{I,II\\}$, we call a vertex $v$ in $V_{i}$ safe
if

(s1) $(v,V(D)\setminus(D_{0}\cup E_{B}))$ is $k$-connected in $D[V_{i}]$,

(s2) $(V(D)\setminus(D_{0}\cup E_{A}),v)$ is $k$-connected in $D[V_{i}]$,

(s3) $(v,V(D)\setminus(D_{0}\cup E_{B}))$ is $k$-connected in
$D[V_{I},V_{II}]$, and

(s4) $(V(D)\setminus(D_{0}\cup E_{A}),v)$ is $k$-connected in
$D[V_{I},V_{II}]$.

The following useful property can be proved by the definition of safe, so we
omit the proof.

###### Property 3.1

For each $\\{i,j\\}=\\{I,II\\}$, the following statements hold.

(i) All colored vertices in $V(D)\setminus(D_{0}\cup E)$ are safe.

(ii) All colored vertices in $V(D)\setminus(D_{0}\cup E_{B})$ satisfy (s1) and
(s3); All colored vertices in $V(D)\setminus(D_{0}\cup E_{A})$ satisfy (s2)
and (s4).

(iii) If $v\in V_{i}$ has at least $k$ out-neighbors of color $i$ satisfying
(s1), then $v$ satisfies (s1); The analogue holds if $v$ has at least $k$ in-
neighbors of color $i$ satisfying (s2).

(iv) If $v\in V_{i}$ has at least $k$ out-neighbors of color $j$ satisfying
(s3), then $v$ satisfies (s3); The analogue holds if $v$ has at least $k$ in-
neighbors of color $j$ satisfying (s4).

The following claim, which will be used frequently in the rest of the proof,
states that to ensure the safety of the colored vertices at some step, we need
to prepare a small set $C^{\prime}$ and a coloring of the vertices in
$C^{\prime}$ such that all colored vertices are safe. In what follows, let
$f(k,l)=k(k+l)\log(2kl)$.

###### Claim 3.1

Let $l^{\prime}\in\mathbb{N}$ with $l^{\prime}\leq 8\cdot 10^{3}f(k,l)$. Let
$C$ be a set of at most $3\cdot 10^{4}(k+l)f(k,l)$ vertices in $V(D)$ such
that $X,Y\subseteq C$. Suppose that $W_{I},W_{II}\subseteq V(D)\setminus C$
are the colored vertex sets of colors $I$ and $II$, respectively, and
$|W_{I}|,|W_{II}|\leq l^{\prime}$. Then there is a set $C^{\prime}\subseteq
V(D)\setminus(C\cup W_{I}\cup W_{II})$ and a coloring of the vertices in
$C^{\prime}$ such that every vertex in $C^{\prime}\cup W_{I}\cup W_{II}$ is
safe and $|C^{\prime}|\leq 2kl^{\prime}+400f(k,l)$.

######  Proof.

To this end, we divide the proof into the following two steps. In Step 1, we
color some vertices in $V(D)\setminus(C\cup W_{I}\cup W_{II})$ such that all
colored vertices satisfy (s3) and (s4). In Step 2, we continue to color some
vertices such that all colored vertices are safe.

Step 1. There exists a vertex set $C_{1}^{\prime}\subseteq V(D)\setminus(C\cup
W_{I}\cup W_{II})$ of size at most

$2k(2k+l+l^{\prime}-2)+100(k+l)\log(2kl)+200f(k,l)$

and a coloring of the vertices in $C_{1}^{\prime}$ such that all vertices in
$C_{1}^{\prime}\cup W_{I}\cup W_{II}$ satisfy (s3) and (s4).

Let $D_{1}=D[W_{I},W_{II}]$ and $l_{0}=l+l^{\prime}$. Since
$|W_{I}|,|W_{II}|\leq l^{\prime}$ and $\delta(D)\geq n-l$, it follows that
$\delta(D_{1})\geq|D_{1}|-l_{0}$. Let $E^{\prime}=C\cup D_{1}\cup D_{0}\cup E$
and $E_{A}^{\prime}=C\cup D_{1}\cup D_{0}\cup E_{A}$. According to (2), (3)
and the upper bound of $|C|$, we obtain

$\displaystyle\hat{\delta}^{+}(D)-|E^{\prime}|\geq 7\cdot
10^{6}(k+l)f(k,l)\text{ and }\hat{\delta}^{-}(D)-|E_{A}^{\prime}|\geq 7\cdot
10^{6}(k+l)f(k,l).$ (4)

By applying Lemma 2.3 to $D_{1}$, there are two sets
$D_{1}^{t},D_{1}^{h}\subseteq D_{1}$ such that

$|D_{1}^{t}|,|D_{1}^{h}|\leq 2k+l_{0}-2\text{ and for each }v\in
D_{1},(v,D_{1}^{h})\text{ and }(D_{1}^{t},v)\text{ are }k\text{-connected in
}D_{1}.$ (5)

To finish Step 1, we will find vertex sets $Q^{\prime},Q,Q_{1},Q_{2}$, and add
vertex sets $Q^{\prime},Q,Q_{1},Q_{2}$ in turn into $D_{1}$ so that all
colored vertices satisfy (s3) and (s4). So $C_{1}^{\prime}=Q^{\prime}\cup
Q\cup Q_{1}\cup Q_{2}$.

Step 1.1. Eq.(4) implies that for each $u\in D_{1}^{h}$, we may greedily
choose a set $Q^{\prime}_{u}\subseteq N^{+}_{D}(u)\setminus E^{\prime}$ with
$|Q^{\prime}_{u}|=k$ and $Q^{\prime}_{u}\cap
Q^{\prime}_{u^{\prime}}=\emptyset$ for any $u^{\prime}\in
D_{1}^{h}\setminus\\{u\\}$. Then color the vertices in $Q^{\prime}_{u}$ the
different color from $u$. Let $Q^{\prime}=\bigcup_{u\in
D_{1}^{h}}Q^{\prime}_{u}$. This yields that for each $u\in D_{1}^{h}$, the
pair $(u,Q^{\prime})$ is $k$-connected in $D[V_{I},V_{II}]$. By (5), we have
that $|Q^{\prime}|\leq k(2k+l_{0}-2)$ and that $(v,Q^{\prime})$ is
$k$-connected in $D[V_{I},V_{II}]$ for each $v\in D_{1}$. Recall that
$Q^{\prime}\cap(D_{0}\cup E)=\emptyset$, Property 3.1 (i) and (iii) yields
that all vertices in $Q^{\prime}$ are safe and all vertices in $D_{1}$ satisfy
(s3).

Step 1.2. Note that $|Q^{\prime}|\leq k(2k+l_{0}-2)$, in the same way as Step
1.1, we may also greedily choose a set $Q$ outsides $D_{0}\cup
E_{A}^{\prime}\cup Q^{\prime}$ with $|Q|\leq k(2k+l_{0}-2)$ such that each
vertex in $D_{1}^{t}$ has $k$ different color in-neighbors in $Q$, and all
colored vertices in $D_{1}\cup Q$ satisfy (s4).

Fig. 2:  The structure of $D[W_{I}\cup W_{II}]$ at Step 1 in the proof of
Claim 3.1.

Combining this with Step 1.1, it remains to color some uncolored vertices to
ensure that all colored vertices in $Q$ satisfy (s3). For each
$i\in\\{I,II\\}$, let $Q_{i}$ denote the set of vertices colored $i$ in $Q$.
Since $|Q_{i}|\leq|Q|\leq k(2k+l_{0}-2)$, applying Proposition 2.2 to
$D[Q_{i}]$ to find a set $Q_{i}^{\prime}\subseteq Q_{i}$ with
$|Q_{i}^{\prime}|\leq 3(k+l)\log|Q_{i}|\leq 50(k+l)\log(2kl)$ such that every
vertex in $Q_{i}\setminus Q_{i}^{\prime}$ has at least $k$ out-neighbors in
$Q_{i}^{\prime}$. Then we change the color of the vertices in $Q_{i}^{\prime}$
to color $j$, where $\\{i,j\\}=\\{I,II\\}$ (see Fig. 2). This results in that
some vertices in $D_{1}$ may not satisfy (s4), since some vertex $u\in
D_{1}^{t}$ may have less than $k$ in-neighbors with different color from $u$
in $Q$.

However, according to (4) and $|Q\cup Q^{\prime}|\leq 2k(2k+l_{0}-2)\leq
5\cdot 10^{3}(k+l)f(k,l)$, we can still greedily choose a set $Q_{1}\subseteq
V(D)\setminus(Q^{\prime}\cup Q\cup E_{A}^{\prime})$ with $|Q_{1}|\leq
100(k+l)\log(2kl)$, and then color the vertices in $Q_{1}$ such that each
vertex $u\in D_{1}^{t}$ has $k$ in-neighbors with different color from $u$.
Since $Q_{1}\cap E_{A}^{\prime}=\emptyset$, Property 3.1 (ii) and (iv) show
that all vertices in $D_{1}\cup Q_{1}$ satisfy (s4). Therefore, it suffices to
guarantee that the vertices in $Q_{1}\cup Q$ satisfy (s3). Owing to Property
3.1 (iv), if the vertices in $Q_{I}^{\prime}\cup Q_{II}^{\prime}$ satisfy
(s3), then the vertices in $Q$ satisfy (s3). So we just need to ensure that
the vertices in $Q_{I}^{\prime}\cup Q_{II}^{\prime}\cup Q_{1}$ satisfy (s3).

By (4) and $|Q\cup Q^{\prime}\cup Q_{1}|\leq
2k(2k+l_{0}-2)+100(k+l)\log(2kl)\leq 5\cdot 10^{3}(k+l)f(k,l)$ again, we may
greedily choose a set $Q_{2}\subseteq V(D)\setminus(Q\cup Q^{\prime}\cup
Q_{1}\cup E^{\prime})$ with $|Q_{2}|\leq 200f(k,l)$, and then color the
vertices in $Q_{2}$ such that each vertex $v\in Q_{I}^{\prime}\cup
Q_{II}^{\prime}\cup Q_{1}$ has $k$ distinct out-neighbors with different color
from $v$ in $Q_{2}$. Due to Property 3.1 (i), all vertices in $Q_{2}$ are
safe, and then all vertices in $Q_{I}^{\prime}\cup Q_{II}^{\prime}\cup Q_{1}$
satisfy (s3) from Property 3.1 (iv).

Now all colored vertices in $V(D_{1})\cup Q^{\prime}\cup Q\cup Q_{1}\cup
Q_{2}$ satisfy (s3) and (s4). Let $C_{1}^{\prime}=Q^{\prime}\cup Q\cup
Q_{1}\cup Q_{2}$. Then $|C_{1}^{\prime}|\leq
2k(2k+l_{0}-2)+100(k+l)\log(2kl)+200f(k,l)$.

Step 2. There exists a vertex set $C_{2}^{\prime}\subseteq V(D)\setminus(C\cup
W_{I}\cup W_{II}\cup C_{1}^{\prime})$ of size at most $68f(k,l)$ and a
coloring of the vertices in $C_{2}^{\prime}$ such that all vertices in
$W_{I}\cup W_{II}\cup C_{1}^{\prime}\cup C_{2}^{\prime}$ are safe.

Let $W_{I}^{\prime}$ and $W_{II}^{\prime}$ denote the set of vertices in
$W_{I}\cup W_{II}\cup C_{1}^{\prime}$ of colors $I$ and $II$, respectively.
Write $E^{\prime\prime}=C\cup E\cup W_{I}^{\prime}\cup W_{II}^{\prime}\cup
D_{0}$ and $E_{A}^{\prime\prime}=C\cup E_{A}\cup W_{I}^{\prime}\cup
W_{II}^{\prime}\cup D_{0}$. By (2), (3) and Step 1, we obtain

$\displaystyle\hat{\delta}^{+}(D)-|E^{\prime\prime}|\geq 6\cdot
10^{6}(k+l)f(k,l)\text{ and }\hat{\delta}^{-}(D)-|E_{A}^{\prime\prime}|\geq
6\cdot 10^{6}(k+l)f(k,l).$ (6)

Next we will find $W,U^{\prime},U^{\prime\prime},W^{\prime}$, and add vertex
sets $W,U^{\prime},U^{\prime\prime},W^{\prime}$ in turn to $W_{I}^{\prime}$ so
that all vertices in $W_{I}^{\prime}\cup W\cup U^{\prime}\cup
U^{\prime\prime}\cup W^{\prime}$ are safe. Similarly, we can also find some
vertices of order the same as $|W\cup U^{\prime}\cup U^{\prime\prime}\cup
W^{\prime}|$ to ensure the safety of all vertices in $W_{II}^{\prime}$. This
implies $|C_{2}^{\prime}|=2|W\cup U^{\prime}\cup U^{\prime\prime}\cup
W^{\prime}|$.

Applying Lemma 2.3 to $D[W_{I}^{\prime}]$, there is a set $W_{I}^{t}\subseteq
W_{I}^{\prime}$ such that $|W_{I}^{t}|\leq 2k+l-1$ (since $\delta(D)\geq n-l$)
and for each $v\in W_{I}$, the pair $(W_{I}^{t},v)$ is $k$-connected in
$D[W_{I}^{\prime}]$. In a similar way as Step 1.2, we may choose a set $W$
with $|W|\leq k(2k+l-1)$ outside $E_{A}^{\prime\prime}$ such that each vertex
$u\in W_{I}^{t}$ has $k$ in-neighbors with the same color as $u$ in $W$.
Moreover, this together with Step 1 implies that

$\text{all vertices in }W\text{ satisfy }(s2)\text{ and }(s4),\text{ and all
vertices in }W_{I}^{\prime}\text{ satisfy }(s2),(s3),(s4).$ (7)

Fig. 3:  The structure of $D[W_{I}]$ at Step 2 in the proof of Claim 3.1.

Apply Proposition 2.2 to $D[W]$, there is a set $U\subseteq W$ with $|U|\leq
3(k+l)\log|W|\leq 6(k+l)\log(2kl)$ such that every vertex in $W\setminus U$
has at least $k$ out-neighbors in $U$. Now we change the color of the vertices
in $U$ to $II$ (see Fig. 3). This operation results in that

(Q1) some vertices in $W_{I}^{\prime}$ may not satisfy (s2), since some vertex
$u\in W_{I}^{t}$ may have less than $k$ in-neighbors with the same color as
$u$ in $W$, and

(Q2) if all vertices in $U$ satisfy (s3), then all vertices in $W$ satisfy
(s3) by Property 3.1 (iv).

In the same way as Step 1.2, we can still greedily choose an uncolored set
$U^{\prime}$ outside $E_{A}^{\prime}$ with $|U^{\prime}|\leq
6(k+l)\text{log}(2kl)$, and then color the vertices in $U^{\prime}$ by $I$
such that each vertex in $u\in W_{I}^{t}$ has at least $k$ in-neighbors with
the same color as $u$. Property 3.1 (ii) and (iv) show that all vertices in
$W_{I}^{\prime}$ satisfy (s2), and

$\text{all vertices in }U^{\prime}\text{ satisfy }(s2)\text{ and }(s4).$ (8)

Owing to (6), we may also greedily choose an uncolored set $U^{\prime\prime}$
outside $E^{\prime}$ with $|U^{\prime\prime}|\leq 24f(k,l)$ such that each
vertex $v\in U\cup U^{\prime}$ has $2k$ distinct out-neighbors in
$U^{\prime\prime}$, and color $k$ of them by $I$, and $k$ of them by $II$. It
follows from Property 3.1 (i), (iii) and (iv) that all vertices in
$U^{\prime\prime}$ are safe, and all vertices in $U\cup U^{\prime}$ satisfy
(s1) and (s3). By (7), (8) and (Q2), we get that all vertices in $U\cup
U^{\prime}$ are safe, and all vertices in $W$ satisfy (s3). Therefore, it
suffices to guarantee that the vertices in $W\cup W_{I}^{\prime}\setminus U$
satisfy (s1).

Applying Lemma 2.3 to $D[W\cup W_{I}^{\prime}\setminus U]$, there is a set
$W_{I}^{h}\subseteq W\cup W_{I}^{\prime}\setminus U$ such that
$|W_{I}^{h}|\leq 2k+l-1$, and for each $u\in W\cup W_{I}^{\prime}\setminus U$,
the pair $(u,W_{I}^{h})$ is $k$-connected in $D[W\cup W_{I}^{\prime}\setminus
U]$. By (6) and $|W\cup U^{\prime}\cup U^{\prime\prime}|\leq 200(k+l)f(k,l)$,
we may greedily choose a set $W^{\prime}$ outside $E^{\prime\prime}$ in a same
way as Step 1.1 such that $|W^{\prime}|\leq k(2k+l-1)$ and each vertex $u\in
W_{I}^{h}$ has $k$ distinct out-neighbors with the same color as $u$ in
$W^{\prime}$. Moreover, all vertices in $W^{\prime}$ are safe and all vertices
in $W\cup W_{I}^{\prime}\setminus U$ satisfy (s1). Now all colored vertices in
$W_{I}^{\prime}\cup W\cup U^{\prime}\cup U^{\prime\prime}\cup W^{\prime}$ are
safe. So $|C_{2}^{\prime}|\leq 2\cdot(2k(2k+l-1)+6(k+l)\log(2kl)+24f(k,l))\leq
68f(k,l)$.

Set $C^{\prime}=C_{1}^{\prime}\cup C_{2}^{\prime}$. Then

$\displaystyle|C^{\prime}|$ $\displaystyle\leq
2k(2k+l_{0}-2)+100(k+l)\log(2kl)+200f(k,l)+68f(k,l)$ $\displaystyle\leq
2k(l+l^{\prime})+368f(k,l)$ $\displaystyle\leq 2kl^{\prime}+400f(k,l).$

###### Claim 3.2

We can color some vertices outside $D_{0}$ such that every colored vertex is
safe, and the set $C_{1}$ consisting of all vertices colored so far satisfies
$|C_{1}|\leq 10^{3}(k+l)f(k,l)$.

######  Proof.

To prove Claim 3.2, for every $v\in X\cup Y$ we in turn greedily choose $2k$
uncolored in-neighbors and $2k$ uncolored out-neighbors, all distinct from
each other, and color $k$ of the in-neighbors and $k$ of the out-neighbors by
$I$ and the remaining $2k$ in/out-neighbors by $II$. Let $D^{\prime}$ denote
the new colored vertices. Due to Property 3.1 (iii) and (iv), if all vertices
in $D^{\prime}$ are safe, then all vertices in $X\cup Y$ are also safe.

Let $W_{I}$ and $W_{II}$ be the sets of the vertices of colors $I$ and $II$ in
$D_{0}\cup D^{\prime}\setminus(X\cup Y)$, respectively. Then
$|W_{I}|,|W_{II}|\leq 6ck+24k^{2}$. By applying Claim 3.1 with $C=X\cup Y$ and
$l^{\prime}=6ck+24k^{2}$, we obtain

$\displaystyle|C_{1}|$ $\displaystyle\leq
12ck+48k^{2}+2k\cdot(6ck+24k^{2})+400f(k,l)$ $\displaystyle\leq
10^{3}(k+l)f(k,l).$

This completes the proof of Claim 3.2.

###  3.2 Construction of the correct $i$-path

The aim of this subsection is to find the correct $i$-path for all $i\in[6k]$,
and make sure that all vertices in these paths are safe. So, let us first give
the definition of the “correct” $i$-path.

###### Definition 3.2

(Correct $i$-path) For each $i\in[6k]$, an i-path $P_{i}$ is a path from the
head $b_{i}$ of $B_{i}$ to the tail $a_{i}$ of $A_{i}$, and an $i$-path
$P_{i}$ is called correct if $i\in[1,2k]$ or it is odd when $i\in[2k+1,4k]$ or
it is even when $i\in[4k+1,6k]$.

The paths $P_{i}$ that we construct will be either “short” or “long”. A path
is said to be _short_ if its length is at most $1200(k+l)\log(2kl)+3l$.
Otherwise we say it _long_. Firstly, we will try to find the short disjoint
correct $i$-path $P_{i}$ for each $i\in[6k]$. Let $\mathcal{P}_{s}$ be the set
of short disjoint correct $i$-paths satisfying the following properties.

(O1) Int($\mathcal{P}_{s})\subseteq V(D)\setminus C_{1}$.

(O2) For each $i\in[6k]$, $\mathcal{P}_{s}$ contains at most one $i$-path.

(O3) The number of paths in $\mathcal{P}_{s}$ is as large as possible.

Let $I_{s}$ be the set of all indices $i$ for which we have been able to
choose a correct short $i$-path and $L=[6k]\setminus I_{s}$.

###### Claim 3.3

We can color all vertices in $V(\mathcal{P}_{s})$ and some other vertices of
$D$ such that

(i) every colored vertex is safe, and the set $C_{2}$ consisting of all
vertices colored so far satisfies $|C_{2}|\leq 25000(k+l)f(k,l)$,

(ii) for each $i\in L$, any $i$-path whose internal vertices lie in
$V(D)\setminus C_{2}$ has length at least $1200(k+l)\log(2kl)+2$.

######  Proof.

To show this claim, we begin by proving the following statements hold.

$(a)$ For each $i\in L$, there exist at most $l+1$ internally disjoint
$i$-paths of length at most $2l+2$ in $V(D)\setminus(V(\mathcal{P}_{s})\cup
C_{1})$.

_Proof of (a)._ Suppose not, then there exists an index $i_{1}\in L$ such that
$V(D)\setminus(V(\mathcal{P}_{s})\cup C_{1})$ has at least $l+2$ internally
disjoint $i_{1}$-paths of length at most $2l+2$. Let
$P_{i_{1},1},\dots,P_{i_{1},t}$ be these $i_{1}$-paths, where $t\geq l+2$, and
$P_{i_{1},j}=b_{i_{1}}u_{i_{1},j}^{1}\cdots
u_{i_{1},j}^{|P_{i_{1},j}|-2}a_{i_{1}}$ with $j\in[t]$. According to (O3),
these $i_{1}$-paths are incorrect. This implies that $u_{i_{1},t}^{1}$ is not
adjacent to $u_{i_{1},j}^{1}$ for each $j\in[t-1]$, which contradicts that
$\delta(D)\geq n-l$. Hence (a) holds.

For all $i\in[L]$, let $\mathcal{P}_{s}^{\prime}$ be a collection of $i$-paths
in $V(D)\setminus(V(\mathcal{P}_{s})\cup C_{1})$ of length at most $2l+2$.
Then $|\text{Int}(\mathcal{P}_{s}^{\prime})|\leq 16kl^{2}$.

$(b)$ For each $i\in L$, there exists at most one $i$-path whose internal
vertices lie in
$V(D)\setminus(V(\mathcal{P}_{s}\cup\mathcal{P}^{\prime}_{s}))$ and whose
length is at most $1200(k+l)\text{log}(2kl)+1$ such that all these paths are
disjoint.

_Proof of (b)._ Suppose not, then let $P_{i}=b_{i}v_{1}\cdots v_{a}a_{i}$ and
$P_{i}^{\prime}=b_{i}u_{1}\cdots u_{b}a_{i}$ be such two internally disjoint
$i$-paths for some $i\in L$. Owing to (O3) and (a), those paths must be
incorrect and the length of those paths is at least $2l+3$. Since
$\delta(D)\geq n-l$, it follows that there exists a vertex $u_{i_{1}}$ such
that $i_{1}\in[2l]$ is odd, and either $v_{1}u_{i_{1}}\in A(D)$ or
$u_{i_{1}}v_{1}\in A(D)$. We may assume that $v_{1}u_{i_{1}}\in A(D)$, and so
$b_{i}v_{1}u_{i_{1}}u_{i_{1}+1}\cdots u_{b}a_{i}$ is a correct $i$-path which
is disjoint from all the other paths in $\mathcal{P}_{s}$, and its length is
at most $1200(k+l)\text{log}(2kl)+1+2l\leq 1200(k+l)\text{log}(2kl)+3l$,
contrary to (O3). Hence (b) holds.

For all $i\in L$, let $\mathcal{P}_{s}^{\prime\prime}$ be a collection of such
incorrect $i$-paths in (b). Thus the number of paths in
$\mathcal{P}_{s}\cup\mathcal{P}_{s}^{\prime\prime}$ is at most $6k$, and then
$|V(\mathcal{P}_{s}\cup\mathcal{P}_{s}^{\prime\prime})|\leq 7300f(k,l)$.

Now we color all vertices in
$V(\mathcal{P}_{s}\cup\mathcal{P}_{s}^{\prime}\cup\mathcal{P}_{s}^{\prime\prime})$,
and color all vertices in
$\text{Int}(\mathcal{P}_{s}^{\prime}\cup\mathcal{P}_{s}^{\prime\prime})$ by
$I$. If $i\in[2k]\cap I_{s}$, then we color the vertices of $P_{i}$ with the
same color. If $i\in[2k+1,6k]\cap I_{s}$, then we color the vertices on
$P_{i}$ such that the color alternates along the orientation of $P_{i}$.
Together with Claim 3.1 (applied with $C=C_{1}$ and
$l^{\prime}=7300f(k,l)+16kl^{2}$) and Claim 3.2, this implies that every
colored vertex is safe, and
$|C_{2}|\leq|C_{1}|+7300f(k,l)+16kl^{2}+2k\cdot(7300f(k,l)+16kl^{2})+400f(k,l)\leq
25000(k+l)f(k,l)$.

Set $D^{\prime}=(D\setminus C_{2})\cup\bigcup_{i\in L}(a_{i}\cup b_{i})$.
Recall that $D$ is a strongly $10^{7}(k+l)f(k,l)$-connected digraph, Claim 3.3
(i) implies that $D^{\prime}$ is strongly $96(k+l)\cdot
10^{5}f(k,l)$-connected. Theorem 2.1 implies that $D^{\prime}$ is
$192000kf(k,l)$-linked. Together with Proposition 2.1 (i) and Claim 3.3 (ii),
this implies that for each $i\in L$ we can find $32000f(k,l)$ $i$-paths in
$D^{\prime}$ such that all these $32000f(k,l)|L|$ paths whose internal
vertices avoid $C_{2}$ have length at least $1200(k+l)\log(2kl)+2$, and are
internally disjoint.

Proposition 2.1 (ii) yields that for all $i\in L$ there exists $800f(k,l)$
internally disjoint $i$-paths such that the number of all vertices in these
$i$-paths is at most $(n-|C_{2}|)/40$. We choose this collection of
$800f(k,l)|L|$ paths such that the length of these paths is minimal. Set
$L_{0}=[800f(k,l)]$.

For all $i\in L$ and all $j\in L_{0}$, let $P_{i,j}$ denote the $j$th $i$-path
we have chosen. Then

$|\bigcup\limits_{(i,j)\in L\times
L_{0}}\text{Int}(P_{i,j})|\leq\frac{n}{40}.$ (9)

Let $P^{1}_{i,j},P^{2}_{i,j},P^{3}_{i,j}$ be disjoint segments of the interior
of $P_{i,j}$ so that $P_{i,j}=b_{i}P^{1}_{i,j}P^{2}_{i,j}P^{3}_{i,j}a_{i}$,
and

$|P^{1}_{i,j}|=|P^{3}_{i,j}|=600(k+l)\log(2kl).$ (10)

Write

$\displaystyle P^{\alpha}=\bigcup\limits_{(i,j)\in L\times
L_{0}}V(P^{\alpha}_{i,j})\text{ with }\alpha\in[3],\text{ and
}P_{i,j}=b_{i}v_{i,j}^{1}\cdots v_{i,j}^{|P_{i,j}|-2}a_{i}.$

Owing to (10), we obtain

$|P^{1}|=|P^{3}|\leq 600(k+l)\log(2kl)\cdot 6k\cdot 800f(k,l)\leq 4\cdot
10^{6}(2kl)^{6}\leq 2^{22}(2kl)^{6}.$ (11)

Further, for each $(i,j)\in L\times L_{0}$, the fact that $\delta(D)\geq n-l$
and the minimality of these paths implies the following statements, where
$\overline{N}(v)=\\{u\in V(D):u\text{ is not adjacent to }v\\}$.

(A1) Every vertex $v_{i,j}^{t}\in V(P_{i,j})$ dominates
$V(b_{i}P_{i,j}v_{i,j}^{t-2})\setminus\overline{N}(v_{i,j}^{t})$ and is
dominated by $V(v_{i,j}^{t+2}P_{i,j}a_{i})\setminus\overline{N}(v_{i,j}^{t})$.

(A2) If a vertex $u\notin C_{2}\cup P^{1}\cup P^{2}\cup P^{3}$ dominates
$v_{i,j}^{t}\in V(P_{i,j})$ (resp. is dominated by $v_{i,j}^{t}\in
V(P_{i,j})$), then $u$ dominates
$V(b_{i}P_{i,j}v_{i,j}^{t-3})\setminus\overline{N}(u)$ (resp. is dominated by
$V(v_{i,j}^{t+3}P_{i,j}a_{i})\setminus\overline{N}(u)$).

Notice that Proposition 2.1 does not provide any information on the length of
$P^{2}_{i,j}$ for each $(i,j)\in L\times L_{0}$, so we cannot apply Claim 3.1
to find a small set to guarantee the safety of all vertices in
$V(P^{2}_{i,j})$. However, if there exist two subsets $W^{1}_{i,j}\subseteq
V(P^{1}_{i,j})$ and $W^{3}_{i,j}\subseteq V(P^{3}_{i,j})$ with
$|W^{1}_{i,j}|=|W^{3}_{i,j}|=2(k+l+2)$ for each $(i,j)\in L\times L_{0}$ and a
coloring of the vertices in $W_{i,j}^{1}\cup W_{i,j}^{2}$ such that there are
$k+l+2$ vertices colored by $I$, and $k+l+2$ vertices colored by $II$ in each
of $W_{i,j}^{1}$ and $W_{i,j}^{2}$, and each vertex of $W^{1}_{i,j}\cup
W^{3}_{i,j}$ is safe, then (A1) and Property 3.1 (iii)-(iv) imply that all
vertices in $\bigcup_{(i,j)\in L\times L_{0}}V(P^{2}_{i,j})$ will be safe with
whichever color. Moreover, by (A2) and Property 3.1 (iii)-(iv), for an
uncolored vertex $v\in E\setminus(C_{2}\cup P^{1}\cup P^{2}\cup P^{3})$, if it
has an out-neighbor in $V(P_{i,j}^{2})$, then $v$ will satisfy (s1) and (s3)
with whichever color; If it has an in-neighbor in $V(P_{i,j}^{2})$, then $v$
will satisfy (s2) and (s4) with whichever color. This means that we can
guarantee the safety of a few vertices to ensure the safety of more.
Therefore, our aim is to find such two disjoint subsets for each $(i,j)\in
L\times L_{0}$, whose safety can be guaranteed by two disjoint smaller subsets
$P_{I},P_{II}\subseteq P^{1}\cup P^{3}$ (see Claims 3.4 and 3.5).

###### Claim 3.4

There exist two disjoint sets $P_{I},P_{II}\subseteq P^{1}\cup P^{3}$ with
$|P_{I}|,|P_{II}|\leq 90(k+l)\text{log}(2kl)$ such that every vertex in
$P^{1}\cup P^{3}\setminus(P_{I}\cup P_{II})$ has at least $k$ out-neighbors
and at least $k$ in-neighbors in each of $P_{I}$ and $P_{II}$.

######  Proof.

To prove this claim, apply Proposition 2.2 and (11) to $D[P^{1}\cup P^{3}]$ to
find a set $P_{I}\subseteq P^{1}\cup P^{3}$ with $|P_{I}|\leq
3(k+l)\log(2^{23}(2kl)^{6})\leq 90(k+l)\log(2kl)$ such that every vertex in
$P^{1}\cup P^{3}\setminus P_{I}$ has at least $k$ out-neighbors and at least
$k$ in-neighbors in $P_{I}$. By applying Proposition 2.2 and (11) to
$D[P^{1}\cup P^{3}\setminus P_{I}]$, there exists a set $P_{II}\subseteq
P^{1}\cup P^{3}\setminus P_{I}$ with $|P_{II}|\leq 90(k+l)\log(2kl)$ such that
every vertex in $P^{1}\cup P^{3}\setminus(P_{I}\cup P_{II})$ has at least $k$
out-neighbors and at least $k$ in-neighbors in $P_{II}$. This completes the
proof of Claim 3.4.

Let $L_{1}=\\{(i,j):V(P_{i,j})\cap(P_{I}\cup P_{II})\\}\neq\emptyset$. For all
$(i,j)\in L_{1}$ and $\alpha\in\\{1,3\\}$, define

$U^{\alpha}_{i,j}$ to be a subset of $V(P^{\alpha}_{i,j})\setminus(P_{I}\cup
P_{II})$ with $|U^{\alpha}_{i,j}|=2(k+l+2)$.

This is possible, since $|V(P^{\alpha}_{i,j})\setminus(P_{I}\cup P_{II})|\geq
400(k+l)\text{log}(2kl)$. Further, set $U=\bigcup_{(i,j)\in
L_{1}}U^{1}_{i,j}\cup U^{3}_{i,j}$. It follows from Claim 3.4 that

$|U|\leq 180(k+l)\log(2kl)\cdot 4(k+l+2)\leq 2\cdot 10^{3}(k+l)^{2}\log(2kl).$
(12)

###### Claim 3.5

We may color some uncolor vertices lying outside $U$ such that

(i) all vertices in $P_{I}$ are colored I and all vertices in $P_{II}$ are
colored II,

(ii) all colored vertices are safe, the set $C_{3}^{\prime}$ consisting of the
colored vertices at this step satisfies $|C_{3}^{\prime}\setminus(P_{I}\cup
P_{II})|\leq 580f(k,l)$, and the set $C_{3}$ consisting of all vertices
colored so far satisfies $|C_{3}|\leq 3\cdot 10^{4}(k+l)f(k,l)$,

(iii) all vertices in $P^{1}\cup P^{3}\setminus(P_{I}\cup P_{II})$ will be
safe with whichever color.

######  Proof.

Color the vertices in $P_{I}\cup P_{II}$ as (i) required. According to Claim
3.3 and (12), we have $|C_{2}\cup U|\leq 3\cdot 10^{4}(k+l)f(k,l)$. Apply
Claim 3.1 with $C=C_{2}\cup U$ and $l^{\prime}=90(k+l)\log(2kl)$ to obtain a
set $C^{\prime}\subseteq V(D)\setminus(C_{2}\cup U\cup P_{I}\cup P_{II})$ such
that every vertex in $P_{I}\cup P_{II}\cup C^{\prime}$ is safe, and
$|C_{3}^{\prime}\setminus(P_{I}\cup P_{II})|=|C^{\prime}|\leq
180f(k,l)+400f(k,l)\leq 580f(k,l)$. Combining this with Claims 3.3 and 3.4
yields $|C_{3}|\leq|C_{2}|+|C^{\prime}|+|P_{I}\cup P_{II}|\leq 3\cdot
10^{4}(k+l)f(k,l)$, and then (iii) follows from (i), (ii), Claim 3.4 and
Property 3.1 (iii)-(iv).

Let $L_{2}=\\{(i,j):V(P_{i,j})\cap(C_{3}^{\prime}\setminus(P_{I}\cup
P_{II}))\\}\neq\emptyset$. For all $(i,j)\in L_{2}$ and $\alpha\in\\{1,3\\}$,
define

$V^{\alpha}_{i,j}$ to be a subset of
$V(P^{\alpha}_{i,j})\setminus(C_{3}^{\prime}\setminus(P_{I}\cup P_{II}))$ with
$|V^{\alpha}_{i,j}|=2(k+l+2)$.

This is also possible, since
$|V(P^{\alpha}_{i,j})\setminus(C_{3}^{\prime}\setminus(P_{I}\cup P_{II}))|\geq
20f(k,l)$. Set $V=\bigcup_{(i,j)\in L_{2}}V^{1}_{i,j}\cup V^{3}_{i,j}$. It
follows from Claim 3.5 (ii) that

$|V|\leq 580f(k,l)\cdot 4(k+l+2)\leq 5\cdot 10^{3}(k+l)f(k,l).$ (13)

###### Claim 3.6

For $(i,j)\in L_{1}\cup L_{2}$ and $\alpha\in\\{1,3\\}$ we may color all
vertices in $U_{i,j}^{\alpha}\cup V_{i,j}^{\alpha}$ such that

(i) there are $k+l+2$ vertices colored by I, and $k+l+2$ vertices colored by
II in each of $U_{i,j}^{\alpha}$ and $V_{i,j}^{\alpha}$ (see Fig. 4),

(ii) all colored vertices are safe, and the set $C_{4}$ consisting of all
vertices colored so far satisfies $|C_{4}|\leq 4\cdot 10^{4}(k+l)f(k,l)$,

(iii) all vertices in $V(P^{2}_{i,j})\setminus(U\cup V)$ will be safe with
whichever color.

######  Proof.

Recall that $|U^{\alpha}_{i,j}|=|V^{\alpha}_{i,j}|=2(k+l+2)$, so we can color
the vertices in $U_{i,j}^{\alpha}\cup V_{i,j}^{\alpha}$ such that (i) holds
(see Fig. 4). Moreover, $U^{\alpha}_{i,j}\cup V^{\alpha}_{i,j}\subseteq
P^{1}\cup P^{3}\setminus(P_{I}\cup P_{II})$, this together with Claim 3.5
(iii), (12) and (13) implies that all colored vertices in
$U_{i,j}^{\alpha}\cup V_{i,j}^{\alpha}$ are safe, and $|C_{4}|\leq 4\cdot
10^{4}(k+l)f(k,l)$. Hence (ii) holds, and then (iii) follows from (i), (ii),
(A1) and Property 3.1 (iii)-(iv). This completes the proof of Claim 3.6.

Fig. 4:  The structure of $P_{i,j}$ with $(i,j)\in L\times L_{0}$.

Recall that for each $i\in L$ there are $800f(k,l)$ internally disjoint
$i$-paths, Claims 3.4 and 3.5 (ii) state that $|C_{3}^{\prime}|\leq
760f(k,l)$. This implies that for all $i\in L$ there exist at least $40f(k,l)$
internally disjoint $i$-paths whose internal vertices avoid $C_{4}$. Next, for
all $i\in L$ we will use $5l$ such $i$-paths to construct one correct
$i$-path; assume they are $P_{i,1},\dots,P_{i,5l}$.

For all $(i,j)\in L\times L_{0}\setminus(L_{1}\cup L_{2})\\}$ and all
$\alpha\in\\{1,3\\}$, let
$P^{\alpha,1}_{i,j},P^{\alpha,2}_{i,j},P^{\alpha,3}_{i,j}$ be disjoint
segments of $P^{\alpha}_{i,j}$ so that
$P^{\alpha}_{i,j}=P^{\alpha,1}_{i,j}P^{\alpha,2}_{i,j}P^{\alpha,3}_{i,j}$ (see
Fig. 4), and

$|P^{\alpha,1}_{i,j}|=|P^{\alpha,3}_{i,j}|=2(k+l+2).$

By (10), we obtain

$|P^{\alpha,2}_{i,j}|\geq 4(k+l+1).$ (14)

Further, let

$\displaystyle L_{3}=\\{(i,j):(i,j)\in L\times\\{1,\ldots,5l\\}\\}\text{ and
}L_{4}=\\{(i,j):(i,j)\in L\times L_{0}\setminus(L_{1}\cup L_{2}\cup
L_{3})\\}.$

Analysis similar to that in the proof of Claim 3.6 shows the following
statements hold.

###### Claim 3.7

For all $(i,j)\in L_{4}$ we may color all vertices in $V(P_{i,j}^{1,1}\cup
P_{i,j}^{3,3})$ such that

(i) the color of the vertices on $P_{i,j}^{1,1}$ (resp. $P_{i,j}^{3,3}$)
alternates along the orientation of $P_{i,j}^{1,1}$ (resp. $P_{i,j}^{3,3}$)
(see Fig. 4), and all colored vertices are safe,

(ii) all vertices in $V(P_{i,j})\setminus V(P_{i,j}^{1,1}\cup P_{i,j}^{3,3})$
will be safe with whichever color.

Recall that $P_{i,j}=b_{i}v_{i,j}^{1}\cdots v_{i,j}^{|P_{i,j}|-2}a_{i}$, for
each $i\in[L]$ consider the subdigraph $D_{i}$ of $D$ induced by
$v_{i,j}^{|P_{i,j}|-2k-2l-6}$ (the last vertex of $P^{3,2}_{i,j}$) for
$j\in[5l]$. Eq.(14) and the fact that $\delta(D)\geq n-l$ shows the following
statements hold, where $j_{1},j_{2},j_{3},j_{4}\in[5l]$ and $\gamma$ is an
even integer.

(B1) The subdigraph $D_{i}$ has at least two vertices of out-degree at least
two; assume they are $v_{i,j_{1}}^{|P_{i,j_{1}}|-2k-2l-6}$ and
$v_{i,j_{2}}^{|P_{i,j_{2}}|-2k-2l-6}$. Further, assume
$v_{i,j_{2}}^{|P_{i,j_{2}}|-2k-2l-6}$ dominates
$v_{i,j_{3}}^{|P_{i,j_{3}}|-2k-2l-6}$ and
$v_{i,j_{1}}^{|P_{i,j_{1}}|-2k-2l-6}$ dominates
$v_{i,j_{4}}^{|P_{i,j_{4}}|-2k-2l-6}$, where $j_{4}\neq j_{2}$ and $j_{3}\neq
j_{1}$.

(B2) $v_{i,j_{1}}^{2k+2l+5}$ dominates $v_{i,j_{2}}^{2k+2l+4+\gamma}$, or
$v_{i,j_{2}}^{2k+2l+4+\gamma}$ dominates $v_{i,j_{1}}^{2k+2l+5}$; assume
$v_{i,j_{1}}^{2k+2l+5}$ dominates $v_{i,j_{2}}^{2k+2l+6}$.

###### Claim 3.8

For each $i\in L$ there is a correct i-path $P_{i}$ (see Fig. 5) such that

(i) all vertices in $\text{Int}(P_{i})$ have not been colored, and $P_{i}$ and
$P_{i^{\prime}}$ are disjoint whenever $i\neq i^{\prime}$,

(ii) if $i\in L\cap[2k]$, then
$P_{i}=b_{i}P_{i,j_{1}}^{1,1}v_{i,j_{1}}^{2k+2l+5}v_{i,j_{2}}^{2k+2l+6}\cdots
v_{i,j_{2}}^{|P_{i,j_{2}}|-2k-2l-6}v_{i,j_{3}}^{|P_{i,j_{3}}|-2k-2l-6}P_{i,j_{3}}^{3,3}a_{i}$
where $j_{1},j_{2},j_{3}\in[5l]$,

(iii) if $i\in L\cap[2k+1,6k]$, then either $P_{i}=P_{i,j}$ for some
$j\in[5l]$, or
$P_{i}=b_{i}P_{i,j_{1}}^{1,1}v_{i,j_{1}}^{2k+2l+5}v_{i,j_{2}}^{2k+2l+6}\cdots$
$v_{i,j_{2}}^{|P_{i,j_{2}}|-2k-2l-6}v_{i,j_{3}}^{|P_{i,j_{3}}|-2k-2l-6}P_{i,j_{3}}^{3,3}a_{i}$
where $j_{1},j_{2},j_{3}\in[5l]$.

######  Proof.

Obviously, (i) and (ii) hold. Suppose that $i\in L\cap[2k+1,6k]$. If there
exists a correct $i$-path among $P_{i,j}$ where $j\in[5l]$, then we take it to
be $P_{i}$. Otherwise, let $P_{i}$ be as described in (iii) (see Fig. 5). This
completes the proof of Claim 3.8.

###### Claim 3.9

For all $(i,j)\in L_{3}$ we may color all vertices in $V(P_{i}\cup
P^{1}_{i,j}\cup P^{3}_{i,j})$ such that

(i) all colored vertices are safe, and the set $C_{5}$ consisting of all
vertices colored so far has size $|C_{5}|\leq 4\cdot 10^{4}(k+l)f(k,l)+n/40$
and

$|C_{5}\setminus(\bigcup_{(i,j)\in L_{3}}V(P_{i,j}^{2})\cup\bigcup_{(i,j)\in
L_{4}}V(P_{i,j}^{1,1}\cup P_{i,j}^{3,3}))|\leq 8\cdot 10^{4}(k+l)f(k,l),$

(ii) every vertex in $V(P_{i,j}^{2})$ will be safe with whichever color, and

(iii) for an uncolored vertex $v\notin P^{1}\cup P^{2}\cup P^{3}$, if it has
an out-neighbor in $V(P_{i,j}^{2})$, then $v$ will satisfy (s1) and (s3) with
whichever color; If it has an in-neighbor in $V(P_{i,j}^{2})$, then $v$ will
satisfy (s2) and (s4) with whichever color.

######  Proof.

First we color the vertices in $P_{i}$ for each $i\in L$. If $i\in L\cap[k]$,
we color the vertices on $P_{i}$ by $I$; If $i\in L\cap[k+1,2k]$, we color the
vertices on $P_{i}$ by $II$; If $i\in L\cap[2k+1,6k]$, we color the vertices
on $P_{i}$ alternating along the orientation of $P_{i}$.

For each $(i,j)\in L_{3}$, color all vertices in $V(P_{i,j}^{1,1}\cup
P_{i,j}^{3,3})\setminus V(P_{i})$ such that there are $k+l+2$ vertices colored
by $I$, and $k+l+2$ vertices colored by $II$ in each of $V(P_{i,j}^{1,1})$ and
$V(P_{i,j}^{3,3})$ (see Fig. 5). We color all vertices in $V(P_{i,j}^{1,2}\cup
P_{i,j}^{3,2})\setminus V(P_{i})$ by $I$, and color all vertices in
$V(P_{i,j}^{1,3}\cup P_{i,j}^{3,1})\setminus V(P_{i})$ by $II$ (see Fig. 5).

It follows from (A1) that each vertex in $V(P^{2}_{i,j})$ has at least $k$
out-neighbors in each color in $V(P_{i,j}^{1})$, and at least $k$ in-neighbors
in each color in $V(P_{i,j}^{3})$. By Claim 3.5 (iii), all colored vertices in
$P^{1}\cup P^{2}$ are safe. This together with Property 3.1 (iii)-(iv) yields
that (ii) holds, and all colored vertices are safe. By (A2) and Property 3.1
(iii)-(iv), we obtain that (iii) holds.

Owing to Claims 3.5–3.7, all colored vertices belong to $C_{3}\cup P^{1}\cup
P^{2}\cup P^{3}$. It follows from (9) that $|C_{5}|\leq|C_{3}\cup P^{1}\cup
P^{2}\cup P^{3}|\leq 3\cdot 10^{4}(k+l)f(k,l)+n/40$. Further, we have

$\displaystyle|C_{5}\setminus(\bigcup_{(i,j)\in
L_{3}}V(P_{i,j}^{2})\cup\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1}\cup
P_{i,j}^{3,3}))|=|C_{5}|+|\bigcup_{(i,j)\in L_{3}}V(P_{i,j}^{1}\cup
P_{i,j}^{3})|$ $\displaystyle\overset{(\ref{13})}{\leq}$ $\displaystyle 4\cdot
10^{4}(k+l)f(k,l)+6k\cdot 5l\cdot 1200(k+l)\log(2kl)$ $\displaystyle\leq$
$\displaystyle 8\cdot 10^{4}(k+l)f(k,l).$

This completes the proof of Claim 3.9.

Fig. 5: Color patterns of the paths int($P_{i}$) with $i\in L\cap[6k]$ and
$l=1$. The black arrows indicate $P_{i}$.

###  3.3 Coloring of the vertices in $E$

In this subsection, we will distribute these vertices in exceptional sets into
$V_{1}$ and $V_{2}$ so that these vertices are safe. Let
$W=\\{w:w\in\bigcup_{(i,j)\in L\times L_{0}}V(P_{i,j})\setminus C_{5}\\}$.
According to Claims 3.5 (iii), 3.6 (iii), 3.7 (ii) and 3.9 (ii), we obtain the
following holds.

###### Claim 3.10

All vertices in $W$ will be safe with whichever color.

Finally, it suffices to deal with the uncolored vertices in $E\setminus W$.

###### Claim 3.11

We may color all vertices in $E\setminus W$ such that all colored vertices are
safe, and the set $C_{6}$ consisting of all vertices colored so far satisfies
$|C_{6}|\leq n/20$.

######  Proof.

We divide the proof of this claim into the following two steps. We first deal
with all vertices in $E_{A}\setminus(C_{5}\cup W)$ (see Step 1) such that all
the vertices in $E_{A}\setminus(C_{5}\cup W)$ satisfy (s2) and (s4). Property
3.1 (ii) yields that all vertices in $E_{A}\setminus E_{B}$ satisfy (s1) and
(s3), and all vertices in $E_{B}\setminus E_{A}$ satisfy (s2) and (s4). After
Step 1, all vertices in $E_{A}\setminus E_{B}$ are safe, and all vertices in
$E_{A}\cap E_{B}$ satisfy (s2) and (s4). This implies that all vertices in
$E_{B}$ satisfy (s2) and (s4). At Step 2, we color each vertex in
$E_{B}\setminus(C_{5}\cup W)$ such that all the vertices in
$E_{B}\setminus(C_{5}\cup W)$ satisfy (s1) and (s3). Then all vertices in
$E\setminus(C_{5}\cup W)$ are safe.

Step 1. We can color each vertex in $E_{A}\setminus(C_{5}\cup W)$ in turn as
well as some set $Z_{A}$ of additional vertices such that all the vertices in
$E_{A}\setminus(C_{5}\cup W)$ satisfy (s2) and (s4). At first, let
$Z_{A}=\emptyset$. At each iteration, we will update $Z_{A}$ such that

(a) $Z_{A}$ consists of colored vertices and $Z_{A}\cap(C_{5}\cup
E_{A})=\emptyset$,

(b) every colored vertex lies in $C_{5}\cup E_{A}\cup Z_{A}$,

(c) $|Z_{A}|\leq 2k|E_{A}|$.

Now suppose that we have already colored some vertices in
$E_{A}\setminus(C_{5}\cup W)$ such that $Z_{A}$ satisfies (a)-(c). It follows
from (2), (3) and Claim 3.9 (i) that

$\displaystyle\hat{\delta}^{-}(D)-|E_{A}\cup
Z_{A}|-|C_{5}\setminus(\bigcup_{(i,j)\in
L_{3}}V(P_{i,j}^{2})\cup\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1}\cup
P_{i,j}^{3,3}))|$ $\displaystyle\geq$
$\displaystyle\hat{\delta}^{-}(D)-3k|E_{A}|-|C_{5}\setminus(\bigcup_{(i,j)\in
L_{3}}V(P_{i,j}^{2})\cup\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1}\cup
P_{i,j}^{3,3}))|$ $\displaystyle\geq$ $\displaystyle 2500(k+l)f(k,l)+2k.$ (15)

Since all colored vertices lie in $C_{5}\cup E_{A}\cup Z_{A}$, eq.(Proof)
implies that for a vertex $v\in E_{A}\setminus(C_{5}\cup W)$, it satisfies one
of the following statements.

(D1) It has at least an in-neighbor in $\bigcup_{(i,j)\in
L_{3}}V(P_{i,j}^{2})$.

(D2) It has at least $2k$ uncolored in-neighbors $v_{1},v_{2},\ldots,v_{2k}$
outside $E_{A}$.

(D3) It has at least $2500k(k+l)^{2}\log(2kl)$ in-neighbors in
$\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1}\cup P_{i,j}^{3,3})$.

First we consider case (D1). Claim 3.9 (iii) yields that $v$ satisfies (s2)
and (s4). We color $v$ with $I$, and $Z_{A}$ stays the same. Then we move to
(D2). We color $k$ of $v_{1},v_{2},\ldots,v_{2k}$ by $I$ and $k$ of them by
$II$, and replace $Z_{A}$ by $Z_{A}\cup\\{v_{1},v_{2},\ldots,v_{2k}\\}$. We
also color $v$ with $I$. It follows from Property 3.1 (ii) and (iv) that all
vertices in $\\{v,v_{1},v_{2},\ldots,v_{2k}\\}$ satisfy (s2) and (s4).

Finally, we turn to (D3). Recall that $|P_{i,j}^{3,3}|=2(k+l+2)$, so for all
$(i,j)\in L_{4}$ let $(i,j)_{l}$ denotes the vertex in $V(P_{i,j}^{3,3})$
where $l\in[2k+2l+4]$. Moreover, write

$P_{i,j}^{3,3}=(i,j)_{2k+2l+4}(i,j)_{2k+2l+3}\cdots(i,j)_{2}(i,j)_{1}.$

Suppose that the vertex $(i,j)_{l_{i,j}}$ is the first vertex in
$V(P_{i,j}^{3,3})$ such that $(i,j)_{l_{i,j}}v\in A(D)$ along the orientation
of $P_{i,j}^{3,3}$. Claim 3.7 (i) states that the color of the vertices in
$V(P_{i,j}^{3,3})$ alternates along the orientation of $P_{i,j}^{3,3}$. Since
$\delta(D)\geq n-l$, it follows from (A2) that there are at least $\lfloor
l_{i,j}/2\rfloor-l-2$ vertices of color $I$ belonging to the in-neighborhood
of $v$, and at least $\lfloor l_{i,j}/2\rfloor-l-2$ vertices of color $II$
belonging to the in-neighborhood of $v$. We see that if $\sum_{(i,j)\in
L_{4}}(\lfloor l_{i,j}/2\rfloor-l-2)\geq k$, then by Claim 3.7 (ii) and
Property 3.1 (iii)-(iv), the vertex $v$ satisfies (s2) and (s4). Thus
$\sum_{(i,j)\in L_{4}}(\lfloor l_{i,j}/2\rfloor-l-2)\leq k-1$. This implies
$\sum_{(i,j)\in L_{4}}l_{i,j}<2500(k+l)f(k,l)$. That is, the in-degree of $v$
in $\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{3,3})$ is less than
$2500k(k+l)^{2}\log(2kl)$. Therefore, $v$ has at least an in-neighbors in
$\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1})$. By Claim 3.7 (iii), we color $v$
with $I$, and $v$ satisfies (s2) and (s4). Then $Z_{A}$ stays the same.

Note that we add at most $2k$ vertices to $Z_{A}$ for each vertex $v\in
E_{A}\setminus(C_{5}\cup W)$. So at the end of Step 1, we will still have
$|Z_{A}|\leq 2k|E_{A}|$.

Step 2. We can color each vertex in $E_{B}\setminus(C_{5}\cup W)$ in turn as
well as some set $Z_{B}$ of additional vertices in such a way that all the
vertices in $E_{B}\setminus(C_{5}\cup W)$ satisfy (s1) and (s3). At first, let
$Z_{B}=\emptyset$. At each substep, we will update $Z_{B}$ such that

($a^{\prime}$) $Z_{B}$ consists of colored vertices and $Z_{B}\cap(C_{5}\cup
E_{B})=\emptyset$,

($b^{\prime}$) every colored vertex lies in $C_{5}\cup E_{B}\cup Z_{B}$,

($c^{\prime}$) $|Z_{B}|\leq 2k|E_{B}|$ and so $|Z|\leq 4k|E_{B}|$, where
$Z=Z_{A}\cup Z_{B}$.

Now suppose that we have already colored some vertices in
$E_{B}\setminus(C_{5}\cup W)$ such that $Z_{B}$ satisfies
($a^{\prime}$)-($c^{\prime}$). Combining this with (2), (3) and Claim 3.9
(iii) implies that

$\displaystyle\hat{\delta}^{+}(D)-|E\cup Z|-|C_{5}\setminus(\bigcup_{(i,j)\in
L_{3}}V(P_{i,j}^{2})\cup\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1}\cup
P_{i,j}^{3,3}))|$ $\displaystyle\geq$
$\displaystyle\hat{\delta}^{+}(D)-5k|E|-|C_{5}\setminus(\bigcup_{(i,j)\in
L_{3}}V(P_{i,j}^{2})\cup\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1}\cup
P_{i,j}^{3,3}))|$ $\displaystyle\geq$ $\displaystyle 2500(k+l)f(k,l)+2k.$ (16)

Since all colored vertices lie in $C_{5}\cup E\cup Z$, eq.(Proof) implies that
for a vertex $v\in E_{B}\setminus(C_{5}\cup W)$, it satisfies one of the
following statements.

(D$1^{\prime}$) It has at least an out-neighbor in $\bigcup_{(i,j)\in
L_{3}}V(P_{i,j}^{2})$.

(D$2^{\prime}$) It has at least $2k$ uncolored out-neighbors
$v_{1},v_{2},\ldots,v_{2k}$ outside $E$.

(D$3^{\prime}$) It has at least $2500k(k+l)^{2}\log(2kl)$ out-neighbors in
$\bigcup_{(i,j)\in L_{4}}V(P_{i,j}^{1,1}\cup P_{i,j}^{3,3})$.

The cases (D$1^{\prime}$)-(D$3^{\prime}$) can be handled in much the same way
as (D1)-(D3). Note that we add at most $2k$ vertices to $Z_{B}$ for each
vertex in $E_{B}\setminus(C_{5}\cup W)$. Thus we always have $|Z_{B}|\leq
2k|E_{B}|$ and so $|Z|\leq 4k|E|$. After Step 2, all colored vertices in
$C_{5}\cup E\setminus W$ are safe, and

$\displaystyle|C_{6}|$
$\displaystyle\leq|C_{5}|+|E|+|Z|\overset{(\ref{1}),(\ref{2})}{\leq}\frac{n}{50}+\frac{n}{40}+\frac{\hat{\delta}^{+}(D)}{1000k}+\frac{4\hat{\delta}^{+}(D)}{1000}\leq\frac{9n}{200}+\frac{\hat{\delta}^{+}(D)}{200}\leq\frac{n}{20}.$

This completes the proof of Claim 3.11.

###  3.4 Construction of sets $V_{1}$ and $V_{2}$

In this subsection, we will construct sets $V_{1}$ and $V_{2}$ as Theorem 1.3
required.

###### Claim 3.12

We may color some additional vertices such that the sets $V_{1}:=V_{I}$ and
$V_{2}:=V_{II}$ as required in Theorem 1.3.

######  Proof.

According to Claim 3.11, the number of all colored vertices is at most $n/20$.
It follows from Property 3.1 (i) and Claim 3.10 that all uncolored vertices
will be safe with whichever color. This implies that we may color some
additional vertices such that $|V_{I}|=n_{1}\geq n/20$, $|V_{II}|=n_{2}\geq
n/20$, and all colored vertices are safe. Therefore, it remains to show the
connectivity of $D[V_{I}]$, $D[V_{II}]$ and $D[V_{I},V_{II}]$.

We first show that $D[V_{I}]$ is strongly $k$-connected. We need to check that
$D[V_{I}\setminus S]$ contains a path from $x$ to $y$ for any set $S$ with
$|S|\leq k-1$ and any two vertices $x,y\in V_{I}\setminus S$. Since each
vertex is safe, (s1) implies that there exists a path $P_{x}$ in
$D[V_{I}\setminus S]$ from $x$ to some vertex $x^{\prime}\in
V_{I}\setminus(D_{0}\cup E_{B}\cup S)$, and (s2) implies that there exists a
path $P_{y}$ in $D[V_{I}\setminus S]$ from some vertex $y^{\prime}\in
V_{I}\setminus(D_{0}\cup E_{A}\cup S)$ to $y$. Without loss of generality
assume $S\cap(A_{1}\cup B_{1}\cup V(P_{1}))=\emptyset$ (recall that $D[A_{1}]$
has a spanning transitive tournament with head $x_{1}$ and tail $a_{1}$,
$D[B_{1}]$ has a spanning transitive tournament with tail $y_{1}$ and head
$b_{1}$, and $P_{1}$ is a path from $b_{1}$ to $a_{1}$). Since
$x^{\prime}\notin D_{0}\cup E_{B}$ and $y^{\prime}\notin D_{0}\cup E_{A}$,
(P3) implies that $x^{\prime}$ sends an arc to $x^{\prime\prime}\in
B_{1}\setminus\\{b_{1}\\}$, and $y^{\prime}$ receives an arc from
$y^{\prime\prime}\in A_{1}\setminus\\{a_{1}\\}$. Altogether this yields that
$D[V(P_{x}\cup P_{y}\cup P_{1})\cup A_{1}\cup B_{1}]\subseteq D[V_{I}\setminus
S]$ contains a path $P_{x}x^{\prime\prime}P_{1}y^{\prime\prime}P_{y}$, as
desired. A similar argument shows that $D[V_{II}]$ is strongly $k$-connected
too.

It remains to show that $D[V_{I},V_{II}]$ is strongly $k$-connected. We will
show that $D[V_{I}\setminus S,V_{II}\setminus S]$ contains a path from $x$ to
$y$ for any set $S$ with $|S|\leq k-1$ and any two vertices $x,y\in
V(D)\setminus S$. Because each vertex is safe, (s3) yields that there exists a
path $P_{x}$ in $D[V_{I}\setminus S,V_{II}\setminus S]$ from $x$ to some
vertex $x^{\prime}\in V(T)\setminus(D_{0}\cup E_{B}\cup S)$, and (s4) yields
that there exists a path $P_{y}$ in $D[V_{I}\setminus S,V_{II}\setminus S]$
from some vertex $y^{\prime}\in V(D)\setminus(D_{0}\cup E_{A}\cup S)$ to $y$.
We now choose an index $i$ as follows:

(i) If $x^{\prime},y^{\prime}\in V_{I}$, let $i\in[2k+1,3k]$ be such that
$S\cap(A_{i}\cup B_{i}\cup V(P_{i}))=\emptyset$.

(ii) If $x^{\prime},y^{\prime}\in V_{II}$, let $i\in[3k+1,4k]$ be such that
$S\cap(A_{i}\cup B_{i}\cup V(P_{i}))=\emptyset$.

(iii) If $x^{\prime}\in V_{I}$ and $y^{\prime}\in V_{II}$, let $i\in[4k+1,5k]$
be such that $S\cap(A_{i}\cup B_{i}\cup V(P_{i}))=\emptyset$.

(iv) If $x^{\prime}\in V_{II}$ and $y^{\prime}\in V_{I}$, let $i\in[5k+1,6k]$
be such that $S\cap(A_{i}\cup B_{i}\cup V(P_{i}))=\emptyset$.

Note that $x^{\prime}\notin D_{0}\cup E_{B}$ and $y^{\prime}\notin D_{0}\cup
E_{A}$, (P3) implies that $x^{\prime}$ sends an arc to $x^{\prime\prime}\in
B_{i}\setminus\\{b_{i}\\}$, and $y^{\prime}$ receives an arc from
$y^{\prime\prime}\in A_{i}\setminus\\{a_{i}\\}$. According to (i)-(iv), the
digraph $D[V_{I}\setminus S,V_{II}\setminus S]$ contains a path
$P_{x}x^{\prime\prime}P_{i}y^{\prime\prime}P_{y}$, as desired.

##  4 Concluding remark

In this section, we obtain that a strongly
$\Omega(k^{3}l^{2}t^{2}\log(2kl))$-connected digraph of order $n$ with
$\delta(D)\geq n-l$ admits a vertex partition into $t$ disjoint sets
$V_{1},V_{2},\ldots,V_{t}$ such that each of $D[V_{1}],\ldots,D[V_{t}]$, and
$D[V_{1},\ldots,V_{t}]$ is strongly $k$-connected. This result can be handled
in much the same way as Theorem 1.3, the only difference being in the
construction and coloring of almost in/out-dominating sets. To prove this
result, we need to construct $(t+4)k$ almost out-dominating sets
$A_{1},\ldots,A_{(t+4)k}$ and $(t+4)k$ almost in-dominating sets
$B_{1},\ldots,B_{(t+4)k}$ satisfy (P0)-(P4). For each $j\in[t]$, define
$j^{*}=[(j-1)k+1,(j-1)k+k]$. Set $D_{j}=\bigcup_{i\in[j^{*}]}(A_{i}\cup
B_{i})$,
$\bigcup\limits_{i\in[tk+1,(t+1)k]}\\{a_{i},b_{i}\\}\cup\bigcup\limits_{i\in[(t+2)k+1,(t+3)k]}\\{b_{i}\\}\cup\bigcup\limits_{i\in[(t+3)k+1,(t+4)k]}\\{a_{i}\\}\subseteq
D_{1}$ and
$\bigcup\limits_{i\in[(t+1)k+1,(t+2)k]}(\\{a_{i},b_{i}\\})\cup\bigcup\limits_{i\in[(t+2)k+1,(t+3)k]}\\{a_{i}\\}\cup\bigcup\limits_{i\in[(t+3)k+1,(t+4)k]}\\{b_{i}\\}\subseteq
D_{2}$ (See figure 1 for $t=2$). Then we can color all vertices in $D_{j}$
with color $j$ and some other vertices such that all colored vertices are
safe. The rest of the proof runs as the proof of Theorem 1.3.

Inspired by the results of Girã and Letzter [3], and Kang and Kim [5], it is
natural to consider the following questions.

###### Conjecture 4.1

There exists a constant $c>0$ such that the vertices of every strongly $c\cdot
ktl$-connected digraph of order $n$ with $\delta(D)\geq n-l$ can be
partitioned into $t$ parts $V_{1},V_{2},\ldots,V_{t}$, each of
$D[V_{1}],\ldots,D[V_{t}]$ and $D[V_{1},\ldots,V_{t}]$ is a strongly
$k$-connected digraph.

###### Conjecture 4.2

Let $k,t,l,m,n,q,a_{1},\ldots,a_{t}\in\mathbb{N}$ with $t,m\geq 2$,
$\sum_{i\in[t]}a_{i}\leq n$ and $a_{i}\geq n/(10tm)$ for each $i\in[t]$.
Suppose that D is a strongly $c\cdot ktlm$-connected digraph of order n with
$\delta(D)\geq n-l$, and $Q_{1},\ldots,Q_{t}\subseteq V(D)$ are t disjoint
sets with $|Q_{i}|\leq q$ for each $i\in[t]$. Then there exist disjoint sets
$W_{1},\ldots,W_{t}$ of $V(D)$ satisfying the following.

(1) $Q_{i}\subseteq W_{i}$.

(2) Each of $D[W_{1}],\ldots,D[W_{t}]$ and $D[W_{1},\ldots,W_{t}]$ is strongly
$k$-connected.

(3) $|W_{i}|=a_{i}$.

##  5 Acknowledgements

We are extremely grateful to the anonymous referees for their careful reading
and suggestions.

## References

  * [1] J. Bang-Jensen, K. Johansen, Every $(13k-6)$-strong tournament with minimum out-degree at least $28k-13$ is $k$-linked, Discrete Math. 345 (2022) 112831.
  * [2] P. Camion, Chemins et circuits hamiltoniens des graphes complets, C. R. Acad. Sci. Paris 249 (1959) 2151–2152.
  * [3] A. Girão, S. Letzter, Partitioning a tournament into sub-tournaments of high connectivity, arXiv:2210.17371V2.
  * [4] P. Hajnal, Partition of graphs with condition on the connectivity and minimum degree, Combinatorica 3 (1983) 95–99.
  * [5] D. Y. Kang, J. Kim, On 1-factors with prescribed lengths in tournaments, J. Combin. Theory Ser. B 141 (2020) 31–71.
  * [6] J. Kim, D. Kühn, D. Osthus, Bipartitions of highly connected tournaments, SIAM J. Discrete Math. 30 (2016) 895–911.
  * [7] D. Kühn, D. Osthus, Partitions of graphs with high minimum degree or connectivity, J. Combin. Theory Ser. B 88 (1) (2003) 29–43.
  * [8] D. Kühn, D. Osthus, T. Townsend, Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths, Combinatorica 36 (2016) 451–469.
  * [9] W. Meng, M. Rolek, Y. Wang, G. Yu, An improved linear connectivity bound for tournaments to be highly linked, European J. Combin. 98 (2021) 103390.
  * [10] J. W. Moon, On subtournaments of a tournament, Canad. Math. Bull. 9 (1966) 297–301.
  * [11] K. B. Reid, Three problems on tournaments, Graph Theory and its applications: East and West, Ann. New York Acad. Sci. 576 (1989) 466–473.
  * [12] C. Thomassen, Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory 7 (1983) 165–167.
  * [13] J. Zhou, Y. Qi, J. Yan, Improved results on linkage probles, Discrete Math. 346 (2023) 113351.