3-Anti-Circulant Digraphs Are α-Diperfect and BE-Diperfect

Lucas I. B. Freitas, Orlando Lee

Institute of Computing, State University of Campinas, Sao Paulo, Brazil.

DOI: 10.4236/ojdm.2022.123003                

Abstract

Let D be a digraph. A subset S of V (D) is a stable set if every pair of vertices in S is non-adjacent in D. A collection of disjoint paths is a path partition of D, if every vertex in V (D) is in exactly one path of . We say that a stable set S and a path partition are orthogonal if each path of contains exactly one vertex of S. A digraph D satisfies the α-property if for every maximum stable set S of D, there exists a path partition such that S and are orthogonal. A digraph D is α-diperfect if every induced subdigraph of D satisfies the α-property. In 1982, Berge proposed a characterization for α-diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture. A digraph D satisfies the Begin-End-property or BE-property if for every maximum stable set S of D, there exists a path partition such that 1) S and are orthogonal and 2) for each path P ∈ , either the start or the end of P belongs to S. A digraph D is BE-diperfect if every induced subdigraph of D satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization for BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this paper, we verified both conjectures for 3-anti-circulant digraphs. We also present some structural results for α-diperfect and BE-diperfect digraphs.

Keywords

3-Anti-Circulant Digraph, Diperfect Digraph, Berge’s Conjecture, Begin-End Conjecture

1. Notation

We assume that the reader is familiar with basic concepts of graph theory. Thus this section is mainly concerned with establishing the notation used. For definitions that are not present in this paper, we refer the reader to Bang-Jensen and Gutin’s book [1] or Bondy and Murty’s book [2].

Let D be a digraph with vertex set $V\left(D\right)$ and arc set $A\left(D\right)$. We only consider finite digraphs without loops and multiple arcs. Given two vertices u and v of $V\left(D\right)$, we denote an arc from u to v by uv. In this case, we say that u dominates v, and we denote this by $u\to v$. We say that u and v are adjacent if $u\to v$ or $v\to u$ ; otherwise, we say that u and v are non-adjacent. If $u\to v$ and $v\to u$, then we denote this by $u\leftrightarrow v$ ; we also say that $\left\{u\mathrm{,}v\right\}$ is a digon. If every pair of distinct vertices of D are adjacent, then we say that D is a semicomplete digraph. A digraph H is a subdigraph of D if $V\left(H\right)\subseteq V\left(D\right)$ and $A\left(H\right)\subseteq A\left(D\right)$ ; moreover, if every arc of $A\left(D\right)$ with both vertices in $V\left(H\right)$ is in $A\left(H\right)$, then we say that H is induced by $X=V\left(H\right)$, and we write $H=D\left[X\right]$. If uv is an arc of D, then we say that u and v are incident in uv. We say that a digraph H is inverse of D if $V\left(H\right)=V\left(D\right)$ and $A\left(H\right)=\left\{uv\mathrm{<mo>\; :\; </mo>}vu\in A\left(D\right)\right\}$. The underlying graph of D, denoted by $U\left(D\right)$, is the simple graph defined by $V\left(U\left(D\right)\right)=V\left(D\right)$ and $E\left(U\left(D\right)\right)=\{uv\mathrm{<mo>\; :\; </mo>}u$ and v are adjacent in $D\}$.

We say that a vertex u is an in-neighbor (resp., out-neighbor) of a vertex v if $u\to v$ (resp., $v\to u$ ). Let X be a subset of $V\left(D\right)$. We denote by $N^{-}\left(X\right)$ (resp., $N^{+}\left(X\right)$ ) the set of vertices in $V\left(D\right)-X$ that are in-neighbors (resp., out-neighbors) of some vertex of X. We define the neighborhood of X as $N\left(X\right)=N^{-}\left(X\right)\cup N^{+}\left(X\right)$ ; when $X=\left\{v\right\}$, we write $N^{-}\left(v\right)$, $N^{+}\left(v\right)$ and $N\left(v\right)$. We say that v is a source if $N^{-}\left(v\right)=\varnothing$ and a sink if $N^{+}\left(v\right)=\varnothing$.

For disjoint subsets X and Y of $V\left(D\right)$ (or subdigraphs of D), we say that X and Y are adjacent if some vertex of X and some vertex of Y are adjacent. Moreover, $X\to Y$ means that every vertex of X dominates every vertex of Y, $X\Rightarrow Y$ means that there exists no arc from Y to X and $X\mapsto Y$ means that both $X\to Y$ and $X\Rightarrow Y$ hold. When $X=\left\{x\right\}$ or $Y=\left\{y\right\}$, we write $x\mapsto Y$ and $X\mapsto y$.

A path P in a digraph D is a sequence of distinct vertices $P=v_1{v}_2\cdots v_k$ such that for all $v_i$ in P, $v_i{v}_{i+1}\in A\left(D\right)$ for $1\le i\le k-1$. Whenever it is appropriate, we treat P as being the subdigraph of D with vertex set $V\left(P\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_k\right\}$ and arc set $A\left(P\right)=\left\{v_i{v}_{i+1}\mathrm{<mo>\; :\; </mo>1}\le i\le k-1\right\}$. We say that P starts at $v_1$ and ends at $v_k$. We also say that $v_1\mathrm{,}{v}_k$ are endvertices of P and $v_1$ is the initial and $v_k$ is the final of P; to emphasize this fact we may write P as $v_{1}P{v}_k$. Also, whenever it is convenient, we may omit the initial or the final in the notation as $v_{1}P$ or $P{v}_k$. We denote by $v_{i}P{v}_j$ a subpath of P where $1\le i\le j\le k$. We define the length of P as $k-1$. We denote by $\stackrel{\leftarrow }{P_k}$ the class of isomorphism of a path of length $k-1$. If $V\left(P\right)=V\left(D\right)$, then we say that P is a Hamilton path of D, and in this case, we say that D is traceable. Let $P\mathrm{,}Q$ be paths in D. If P ends at some vertex v and Q starts at some vertex u such that $v\to u$, then we denote by PQ the concatenation of P and Q. We use this notation only if PQ is a path.

A cycle C in D is a sequence of vertices $C=v_1{v}_2\cdots v_k{v}_1$ such that $v_1{v}_2\cdots v_k$ is a path, $v_k{v}_1\in A\left(D\right)$ and $k\ge 2$. Whenever it is convenient, we also treat C as the subdigraph of D with vertex set $V\left(C\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_k\right\}$ and arc set $A\left(C\right)=\left\{v_i{v}_{i+1}\mathrm{<mo>\; :\; </mo>1}\le i\le k\right\}$ where subscripts are taken modulo k. We define the length of C as k. If k is odd, then we say that C is an odd cycle. We denote by $\stackrel{\leftarrow }{C_k}$ the class of isomorphism of a cycle of length k. If $V\left(C\right)=V\left(D\right)$, then we say that C is a Hamilton cycle of D, and we also say that D is hamiltonian. We say that D is an acyclic digraph if D does not contain cycles. We also say that C is a non-oriented cycle if C is not a cycle in D, but $U\left(C\right)$ is a cycle in $U\left(D\right)$. In particular, if a non-oriented cycle C has length three, then we say that C is a transitive triangle in D.

Let D be a digraph. A subset S of $V\left(D\right)$ is a stable set if every pair of vertices in S is non-adjacent in D. The cardinality of a maximum stable set in D is called the stability number of D and is denoted by $\alpha \left(D\right)$. A collection of disjoint paths $\mathcal{P}$ of D is a path partition of $V\left(D\right)$, if every vertex in $V\left(D\right)$ belongs to exactly one path of $\mathcal{P}$. Let S be a stable set of D. We say that S and $\mathcal{P}$ are orthogonal if $\left|V\left(P\right)\cap S\right|=1$ for every $P\in \mathcal{P}$.

Let G be a connected graph. A clique is a set of pairwise adjacent vertices of G. The clique number of G, denoted by $\omega \left(G\right)$, is the size of maximum clique of G. We say that a vertex set $B\subset V\left(G\right)$ is a vertex cut if $G-B$ is a disconnected graph. If $G\left[B\right]$ is a complete graph, then we say that B is a clique cut. A (proper) coloring of G is a partition of $V\left(G\right)$ into stable sets $\left\{S_1\mathrm{,}\cdots \mathrm{,}{S}_k\right\}$. The chromatic number of G, denoted by $\chi \left(G\right)$, is the cardinality of a minimum coloring of G. We say that G is perfect if for every induced subgraph H of G, the equality $\omega \left(G\right)=\chi \left(H\right)$ holds. Moreover, we say that a digraph D is diperfect if $U\left(D\right)$ is perfect.

2. Introduction

Some very important results in graph theory characterize a certain class of graphs (or digraphs) in terms of certain forbidden induced subgraphs (subdigraphs). The most famous one is probably Berge’s Strong Perfect Graph Conjecture [3]. Berge showed that neither an odd cycle of length at least five nor its complement is perfect. He conjectured that a graph G is perfect if and only if it contains neither an odd cycle of length at least five nor its complement as an induced subdigraph. In 2006, Chudnovsky, Robertson, Seymour and Thomas [4] proved Berge’s conjecture, which became known as the Strong Perfect Graph Theorem.

Theorem 1 (Chudnovsky, Robertson, Seymour and Thomas, 2006). A graph G is perfect if and only if G contains neither an odd cycle of length at least five nor its complement as an induced subgraph.

In this paper we are concerned with two conjectures on digraphs which are somehow similar to Berge’s conjecture. Those conjectures relate path partitions and stable sets. We need a few definitions in order to present both conjectures.

Let S be a stable set of a digraph D. An S-path partition of D is a path partition $\mathcal{P}$ such that S and $\mathcal{P}$ are orthogonal. We say that D satisfies the α-property if for every maximum stable set S of D there exists an S-path partition of D, and we say that D is α-diperfect if every induced subdigraph of D satisfies the α-property. A digraph C is an anti-directed odd cycle if 1) $C=x_1{x}_2\cdots x_{2k+1}{x}_1$ is a non-oriented odd cycle, where $k\ge 2$ and 2) each of the vertices $x_1\mathrm{,}{x}_2\mathrm{,}{x}_3\mathrm{,}{x}_4\mathrm{,}{x}_6\mathrm{,}{x}_8\mathrm{,}\cdots \mathrm{,}{x}_{2k}$ is either a source or a sink (see Figure 1).

Figure 1. Examples of anti-directed odd cycles with length five and seven, respectively.

Berge [5] showed that anti-directed odd cycles do not satisfy the α-property, and hence, they are not α-diperfect, which led him to conjecture the following characterization for α-diperfect digraphs.

Conjecture 1 (Berge, 1982). A digraph D is α-diperfect if and only if D does not contain an anti-directed odd cycle as an induced subdigraph.

Denote by $\mathfrak{B}$ the set of all digraphs which do not contain an induced anti-directed odd cycle. So Berge’s conjecture can be stated as: D is α-diperfect if and only if D belongs to $\mathfrak{B}$. In 1982, Berge [5] verified Conjecture 1 for diperfect digraphs and for symmetric digraphs (digraphs such that if $uv\in A\left(D\right)$, then $vu\in A\left(D\right)$ ). In the next three decades, no results regarding this problem were published (with the exception of a survey by Hartman [6]). In [7] [8], Sambinelli, Silva and Lee verified Conjecture 1 for locally in-semicomplete digraphs and digraphs whose underlying graph is series-parallel. In [9], Freitas and Lee verified Conjecture 1 for arc-locally (out) in-semicomplete digraphs. To the best of our knowledge, these papers are the only ones related to Conjecture 1 that were published recently.

In an attempt to understand the main difficulties in proving Conjecture 1, Sambinelli, Silva and Lee [7] [8] introduced the class of Begin-End-diperfect digraphs, or simply BE-diperfect digraphs, which we define next.

Let S be a stable set of a digraph D. A path partition $\mathcal{P}$ is an S_BE-path partition of D if 1) $\mathcal{P}$ and S are orthogonal and 2) every vertex of S is the initial or the final of a path in $\mathcal{P}$. We say that D satisfies the BE-property if for every maximum stable set of D there exists an S_BE-path partition. We say that D is BE-diperfect if every induced subdigraph of D satisfies the BE-property. Note that if D is BE-diperfect, then it is also α-diperfect, but the converse is not true (see the digraph in Figure 2(b)). A digraph C is a blocking odd cycle if 1) $C=x_1{x}_2\cdots x_{2k+1}{x}_1$ is a non-oriented odd cycle, where $k\ge 1$ and 2) $x_1$ is a source and $x_2$ is a sink (see Figure 2). Note that every anti-directed odd cycle is also a blocking odd cycle.

Figure 2. Examples of blocking odd cycles with length five and three, respectively.

Sambinelli, Silva and Lee [7] [8] showed that blocking odd cycles do not satisfy the BE-property, and hence, they are not BE-diperfect, which led them to conjecture the following characterization of BE-diperfect digraphs.

Conjecture 2 (Sambinelli, Silva and Lee, 2018). A digraph D is BE-diperfect if and only if D does not contain a blocking odd cycle as an induced subdigraph.

Denote by $\mathfrak{D}$ the set of all digraphs which do not contain an induced blocking odd cycle. So Conjecture 2 can be stated as: D is BE-diperfect if and only if D belongs to $\mathfrak{D}$. Sambinelli, Silva and Lee [7] [8] verified Conjecture 2 for locally in-semicomplete digraphs and digraphs whose underlying graph are series-parallel or perfect. In [9], Freitas and Lee verified Conjecture 2 for arc-locally (out) in-semicomplete digraphs. Note that a diperfect digraph belongs to $\mathfrak{D}$ if and only if it contains no induced transitive triangle.

The rest of this paper is organized as follows. In Section 3, we present some structural results for α-diperfect digraphs and BE-diperfect digraphs. In Section 4, we present some structural results for 3-anti-circulant digraphs and we verify both Conjecture 1 and Conjecture 2 for these digraphs. In Section 5, we present some final comments.

3. Some Structural Results

In this section, we present some structural results for BE-diperfect digraphs and α-diperfect digraphs. Let D be a digraph and let S be a maximum stable set of D. Since every S_BE-path partition of D is also an S-path partition, it follows that if D satisfies the BE-property, then D also satisfies the α-property. Moreover, the principle of directional duality states that every structural result in a digraph has a companion structural result in its inverse digraph. Note that a digraph D is BE-diperfect (resp., α-diperfect) if and only if its inverse digraph is BE-diperfect (resp., α-diperfect).

Let us start with the following structural lemma.

Lemma 1. Let D be a digraph such that every proper induced subdigraph of D satisfies the BE-property (resp., α-property). Let S be a maximum stable set in D. Let $P=v_1{v}_2\cdots v_k$ be a path of D such that $V\left(P\right)\cap S=\varnothing$ . If there exists a vertex u in $D-V\left(P\right)$ such that $u\notin S$, $N^{+}\left(u\right)\ne \varnothing$ and $N^{+}\left(u\right)\subseteq V\left(P\right)$, then D admits an S_BE-path partition (resp., S-path partition).

Proof. Let i be the minimum in $\left\{\mathrm{1,2,}\cdots \mathrm{,}k\right\}$ such that $u\to v_i$. Let $P^{\prime }=v_{i}P{v}_k$. Note that $N^{+}\left(u\right)\subseteq V\left(P^{\prime }\right)$. Let $D^{\prime }=D-V\left(P^{\prime }\right)$. Note that u is a sink in $D^{\prime }$. Since $V\left(P^{\prime }\right)\cap S=\varnothing$, S is a maximum stable set in $D^{\prime }$. By hypothesis, $D^{\prime }$ is BE-perfect. Let ${\mathcal{P}}^{\prime }$ be an S_BE-path partition of $D^{\prime }$. Let R be a path in ${\mathcal{P}}^{\prime }$ such that $u\in V\left(R\right)$. Since u is a sink in $D^{\prime }$, it follows that R ends at u. Since $u\to v_i$, the collection $\left({\mathcal{P}}^{\prime }-\left\{R\right\}\right)\cup \left\{R{P}^{\prime }\right\}$ is an S_BE-path partition of D.

By the principle of directional duality, we have the following result.

Lemma 2. Let D be a digraph such that every proper induced subdigraph of D satisfies the BE-property (resp., α-property). Let S be a maximum stable set in D. Let $P=v_1{v}_2\cdots v_k$ be a path of D such that $V\left(P\right)\cap S=\varnothing$ . If there exists a vertex u in $D-V\left(P\right)$ such that $u\notin S$, $N^{-}\left(u\right)\ne \varnothing$ and $N^{-}\left(u\right)\subseteq V\left(P\right)$, then D admits an S_BE-path partition (resp., S-path partition).

The next lemma is similar to Lemma 1, but it provides a different technique.

Lemma 3. Let D be a digraph such that every proper induced subdigraph of D satisfies the BE-property (resp., α-property). Let S be a maximum stable set in D. Let $P=v_1{v}_2\cdots v_k$ be a path of D such that $V\left(P\right)\cap S=\varnothing$ . If there exists an arc $u_1{u}_2$ in $A\left(D\right)$ such that $u_1\notin S$, $\left\{u_1\mathrm{,}{u}_2\right\}\cap V\left(P\right)=\varnothing$, $v_k\to u_2$ and $N^{+}\left(u_1\right)\subseteq V\left(P\right)\cup \left\{u_2\right\}$, then D admits an S_BE-path partition (resp., S-path partition).

Proof. Let i be the minimum in $\left\{\mathrm{1,2},\cdots \mathrm{,}k\right\}$ such that $u_1\to v_i$. Let $P^{\prime }=v_{i}P{v}_k$. Note that $N^{+}\left(u_1\right)\subseteq V\left(P^{\prime }\right)\cup \left\{u_2\right\}$. Let $D^{\prime }=D-V\left(P^{\prime }\right)$. Since $V\left(P^{\prime }\right)\cap S=\varnothing$, S is a maximum stable set in $D^{\prime }$. By hypothesis, $D^{\prime }$ is BE-diperfect. Let ${\mathcal{P}}^{\prime }$ be an S_BE-path partition of $D^{\prime }$. Let R be a path in ${\mathcal{P}}^{\prime }$ such that $u_1\in V\left(R\right)$. If R ends at $u_1$, then since $u_1\to v_i$, it follows that the collection $\left({\mathcal{P}}^{\prime }-\left\{R\right\}\right)\cup \left\{R{P}^{\prime }\right\}$ is an S_BE-path partition of D. So we may assume that P does not end at $u_1$. Since $N^{+}\left(u_1\right)\subseteq V\left(P^{\prime }\right)\cup \left\{u_2\right\}$, it follows that $u_1{u}_2$ is an arc in R. Let $w_1$ and $w_p$ be the endvertices of R. Let $R_1=w_{1}R{u}_1$ and let $R_2=u_{2}R{w}_p$. Since $u_1\to v_i$ and $v_k\to u_2$, the collection $\left({\mathcal{P}}^{\prime }-\left\{R\right\}\right)\cup \left\{R_1{P}^{\prime }{R}_2\right\}$ is an S_BE-path partition of D.

By the principle of directional duality, we have the following result.

Lemma 4. Let D be a digraph such that every proper induced subdigraph of D satisfies the BE-property (resp., α-property). Let S be a maximum stable set in D. Let $P=v_1{v}_2\cdots v_k$ be a path of D such that $V\left(P\right)\cap S=\varnothing$ . If there exists an arc $u_1{u}_2$ in $A\left(D\right)$ such that $u_2\notin S$, $\left\{u_1\mathrm{,}{u}_2\right\}\cap V\left(P\right)=\varnothing$, $u_1\to v_1$ and $N^{-}\left(u_2\right)\subseteq V\left(P\right)\cup \left\{u_1\right\}$, then D admits an S_BE-path partition (resp., S-path partition).

Next, we show that if a digraph D contains a special partition of its vertices, then D admits an S_BE-path partition (resp., S-path partition).

Lemma 5. Let D be a digraph such that every proper induced subdigraph of D satisfies the BE-property (resp., α-property). Let S be a maximum stable set of D. If $V\left(D\right)$ admits a partition $\left(V_1\mathrm{,}{V}_2\mathrm{,}{V}_3\right)$ such that $V_1\mapsto V_2\mapsto V_3$, $D\left[V_2\right]$ is hamiltonian, $\left|V_2\right|\ge 2$ and $\left|V_2\cap S\right|\le 1$, then D admits an S_BE-path partition (resp., S-path partition).

Proof. Let $k=\left|V_2\right|$. Let $C=v_1{v}_2\cdots v_k$ be a Hamilton cycle in $D\left[V_2\right]$. Let B be a subset of $V_2-S$ with cardinality $k-1$ (note that B exists because $\left|V_2\right|\ge 2$ and $\left|V_2\cap S\right|\le 1$ ). Without loss of generality, we may assume that $v_k$ is the vertex in $V_2-B$. Let $D^{\prime }=D-B$. Since $B\cap S=\varnothing$, S is maximum in $D^{\prime }$. By hypothesis, $D^{\prime }$ is BE-diperfect. Let ${\mathcal{P}}^{\prime }$ be an S_BE-path partition of $D^{\prime }$. Let P be a path in ${\mathcal{P}}^{\prime }$ such that $v_k\in V\left(P\right)$. First, suppose that P does not start at $v_k$. Let w be the vertex in P that immediately precedes $v_k$. Let $P_1=Pw$ and let $P_2=v_{k}P$. Since $V_1\mapsto V_2\mapsto V_3$ and $V\left(D^{\prime }\right)\cap V_2=v_k$, it follows that w in $V_1$. Let $R=v_1{v}_2\cdots v_{k-1}$. Since $V_1\mapsto V_2$, it follows that $w\to v_1$. Since $v_{k-1}\to v_k$, we conclude that the collection $\left({\mathcal{P}}^{\prime }-\left\{P\right\}\right)\cup \left\{P_{1}R{P}_2\right\}$ is an S_BE-path partition of D. So we may assume that P starts at $v_k$. Let w be the vertex in P that immediately follows $v_k$. Let $P_1=v_k$ and let $P_2=wP$. Let $R=v_1{v}_2\cdots v_{k-1}$. Since $V_2\mapsto V_3$, it follows that $v_{k-1}\to w$. Since $v_k\to v_1$, we conclude that the collection $\left({\mathcal{P}}^{\prime }-\left\{P\right\}\right)\cup \left\{P_{1}R{P}_2\right\}$ is an S_BE-path partition of D.

Next, we prove some lemmas to α-diperfect digraphs.

Lemma 6. Let D be a digraph such that every proper induced subdigraph of D satisfies the α-property. Let S be a maximum stable set of D. Let $v_1{v}_2$ be an arc of $A\left(D\right)$ . Then,

1) If $v_1\notin S$ and $N^{-}\left(v_2\right)=\left\{v_1\right\}$, then D admits an S-path partition,

2) If $v_2\notin S$ and $N^{+}\left(v_1\right)=\left\{v_2\right\}$, then D admits an S-path partition.

Proof. By the principle of directional duality, it suffices to prove (1). Let $D^{\prime }=D-v_1$. Since $v_1\notin S$, S is a maximum stable set in $D^{\prime }$. By hypothesis, $D^{\prime }$ is α-diperfect. Let ${\mathcal{P}}^{\prime }$ be an S-path partition of $D^{\prime }$. Let P be a path in ${\mathcal{P}}^{\prime }$ such that $v_2\in V\left(P\right)$. Since $N^{-}\left(v_2\right)=\left\{v_1\right\}$, it follows that P starts at $v_2$. Since $v_1\to v_2$, the collection $\left({\mathcal{P}}^{\prime }-\left\{P\right\}\right)\cup \left\{v_{1}P\right\}$ is an S-path partition of D.

Lemma 7. Let D be a digraph such that every proper induced subdigraph of D satisfies the α-property. Let S be a maximum stable set in D. Let $P=v_1{v}_2\cdots v_k$, $k>1$, be a path of D such that $\left(V\left(P\right)-\left\{v_1\right\}\right)\cap S=\varnothing$ . If there exists a vertex u in $D-V\left(P\right)$ such that $v_k\to u$ and $N^{-}\left(u\right)\subseteq V\left(P\right)$, then D admits an S-path partition.

Proof. Let $P^{\prime }=v_{2}P{v}_k$. Let $D^{\prime }=D-V\left(P^{\prime }\right)$. Since $V\left(P^{\prime }\right)\cap S=\varnothing$, S is a maximum stable set in $D^{\prime }$. By hypothesis, $D^{\prime }$ is α-diperfect. Let ${\mathcal{P}}^{\prime }$ be an S-path partition of $D^{\prime }$. Let R be a path in ${\mathcal{P}}^{\prime }$ such that $u\in V\left(R\right)$. Since $N^{-}\left(u\right)\subseteq V\left(P\right)$, it follows that R starts at u or $v_{1}u$ is an arc of R. If P starts at u, then since $v_k\to u$, it follows that the collection $\left({\mathcal{P}}^{\prime }-\left\{R\right\}\right)\cup \left\{P^{\prime }R\right\}$ is an S-path partition of D. So suppose that $v_{1}u$ is an arc of P. Let $w_1$ and $w_p$ be the endvertices of R. Let $R_1=w_{1}R{v}_1$ and let $R_2=uR{w}_p$. Thus the collection $\left({\mathcal{P}}^{\prime }-\left\{R\right\}\right)\cup \left\{R_1{P}^{\prime }{R}_2\right\}$ is an S-path partition of D.

By the principle of directional duality, we have the following result.

Lemma 8. Let D be a digraph such that every proper induced subdigraph of D satisfies the α-property. Let S be a maximum stable set in D. Let $P=v_1{v}_2\cdots v_k$ be a path of D such that $\left(V\left(P\right)-\left\{v_k\right\}\right)\cap S=\varnothing$ . If there exists a vertex u in $D-V\left(P\right)$ such that $u\to v_1$ and $N^{+}\left(u\right)\subseteq V\left(P\right)$, then D admits an S-path partition.

4. 3-Anti-Circulant Digraphs

In this section, we verify both Conjecture 1 and Conjecture 2 for 3-anti-circulant digraphs which we define in this section.

Let D be a digraph. We say that a set $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\subseteq V\left(D\right)$ is an anti-P₄ if $v_1\to v_2$, $v_3\to v_2$ and $v_3\to v_4$. Whenever it is convenient, we may write an anti-P₄ as $v_1\to v_2\leftarrow v_3\to v_4$. Since every anti-directed odd cycle and every blocking odd cycle of length at least five contains an induced anti-P₄, it seems interesting to study digraphs that do not contain anti-P₄ as an induced subdigraph. Motivated by this observation, we study the class of 3-anti-circulant digraphs defined by Wang [10] because they satisfy this property.

Let D be a digraph. We say that D is 3-anti-circulant if for every anti-P₄ $v_1\to v_2\leftarrow v_3\to v_4$ in D, it follows that $v_4\to v_1$ (see Figure 3(a)). Note that the inverse of D is also a 3-anti-circulant digraph. So we can use the principle of directional duality whenever it is convenient. Moreover, note that every 3-anti-circulant digraph belongs to $\mathfrak{B}$, and the only possible induced blocking odd cycle in a 3-anti-circulant digraph is a transitive triangle (see Figure 3(b)).

Figure 3. Examples of 3-anti-circulant digraphs.

Moreover, Wang also characterized the structure of a strong 3-anti-circulant digraph admitting a partition into vertex-disjoint cycles and showed that the structure is very close to semicomplete and semicomplete bipartite digraphs. This characterization does not seem to help in proving both conjectures for these digraphs. So we use a different approach. First, we need the following definitions.

Let S be a maximum stable set of a digraph D. Denote by $B^{+}$ (resp., $B^{-}$ ) the subset of $V\left(D\right)-S$ such that $B\Rightarrow S$ (resp., $S\Rightarrow B$ ). Moreover, let $B^{\pm }=V\left(D\right)-\left(B^{+}\cup B^{-}\cup S\right)$, that is, $B^{\pm }$ is a set of those vertices that both dominate and are dominated by some vertex in S (see Figure 4). Note that $B^{+}$, $B^{-}$ and $B^{\pm }$ are pairwise disjoint and since S is a maximum stable set in D, it follows that $V\left(D\right)=S\cup B^{+}\cup B^{-}\cup B^{\pm }$.

Figure 4. Illustration of $B^{+}$, $B^{\pm }$ and $B^{-}$.

Let us start with a simple and useful structural lemma.

Lemma 9. Let D be a 3-anti-circulant digraph. Let S be a maximum stable set in D. Then, for every v in $B^{+}$ and for every u in $B^{-}$, it follows that $\left|N^{-}\left(v\right)\cap B^{+}\right|\le 1$ and $\left|N^{+}\left(u\right)\cap B^{-}\right|\le 1$ .

Proof. Note that by the principle of directional duality, it suffices to show that $\left|N^{-}\left(v\right)\cap B^{+}\right|\le 1$. Towards a contradiction, suppose that $\left|N^{-}\left(v\right)\cap B^{+}\right|>1$. So let $v_1\mathrm{,}{v}_2$ be vertices in $N^{-}\left(v\right)\cap B^{+}$. By definition of $B^{+}$, there exists a vertex y in S such that $v_1\to y$. Since $v_2\to v\leftarrow v_1\to y$ and D is 3-anti-circulant, it follows that $y\to v_2$, a contradiction because $v_2\in B^{+}$. Thus $\left|N^{-}\left(v\right)\cap B^{+}\right|\le 1$ and $\left|N^{+}\left(u\right)\cap B^{-}\right|\le 1$.

4.1. Begin-End Conjecture

In this subsection, we verify Conjecture 2 for 3-anti-circulant digraphs. In order to do this, we need the following auxiliary result by Freitas and Lee [9].

Lemma 10 (Freitas and Lee, 2021). Let D be a digraph such that every proper induced subdigraph of D satisfies the BE-property (resp., α-property). If D has a stable set S such that $\left|N\left(S\right)\right|\le \left|S\right|$, then D satisfies the BE-property (resp., α-property).

Initially, we present an outline of the main proof. Let D be 3-anti-circulant digraph and let S be a maximum stable set in D. Note that every induced subdigraph of D is also a 3-anti-circulant digraph. Thus it suffices to show that D satisfies the BE-property. First, we show that if $D\in \mathfrak{D}$, then there exists no arc connecting vertices of distinct sets in $B^{+}$, $B^{-}$ and $B^{\pm }$. Next, we show that $B^{+}$, $B^{-}$ and $B^{\pm }$ are stable. This implies that $\left|S\right|\ge \left|B^{+}\cup B^{-}\cup B^{\pm }\right|$, and hence, it follows by Lemma 10 that D satisfies the BE-property.

In the next three lemmas we show that if $U\left(D\right)$ contains a cycle C of length three such that C contains a digon and $V\left(C\right)\cap S\ne \varnothing$, then D admits an S_BE-path partition.

Lemma 11. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. Let $v_1\leftrightarrow v_2$ be a digon in $D-S$ . If there exists a vertex $v_3$ in $V\left(D\right)-\left\{v_1\mathrm{,}{v}_2\right\}$ such that $v_3\in S$ and $D\left[\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\right]$ contains a $\stackrel{\leftarrow }{C_3}$, then D admits an S_BE-path partition.

Proof. With loss of generality, assume that $v_2\to v_3$ and $v_3\to v_1$. Let $D^{\prime }=D-\left\{v_1,v_2\right\}$. Since $\left\{v_1\mathrm{,}{v}_2\right\}\cap S=\varnothing$, S is a maximum stable set in $D^{\prime }$. By hypothesis, $D^{\prime }$ is BE-diperfect. Let ${\mathcal{P}}^{\prime }$ be an S_BE-path partition of $D^{\prime }$. Let P be a path in ${\mathcal{P}}^{\prime }$ such that $v_3\in V\left(P\right)$. If $V\left(P\right)=\left\{v_3\right\}$, then the collection $\left({\mathcal{P}}^{\prime }-\left\{v_3\right\}\right)\cup \left\{v_1{v}_2{v}_3\right\}$ is an S_BE-path partition of D. So we may assume that $\left|V\left(P\right)\right|>1$. By the principle of directional duality, we may assume that P starts at $v_3$. Let $P=v_3{w}_1{w}_2\cdots w_k$. Next, we show by induction on k that $w_k\to v_1$ or $w_k\to v_2$ holds. First, suppose that $k=1$. Since $v_2\to v_1\leftarrow v_3\to w_1$ and D is 3-anti-circulant, it follows that $w_1\to v_2$. Now, assume that $k>1$. By induction hypothesis, $w_{i-1}\to v_1$ or $w_{i-1}\to v_2$ for some $i\in \left\{2,\cdots \mathrm{,}k\right\}$. Since $v_1\leftrightarrow v_2$ and $w_{i-1}\to w_i$, it follows that $w_i\to v_1$ or $w_i\to v_1$. Thus $w_k\to v_1$ or $w_k\to v_2$. Since $v_1\leftrightarrow v_2$, the collection $\left({\mathcal{P}}^{\prime }-\left\{P\right\}\right)\cup \left\{P{v}_1{v}_2\right\}$ or $\left({\mathcal{P}}^{\prime }-\left\{P\right\}\right)\cup \left\{P{v}_2{v}_1\right\}$ is an S_BE-path partition of D.

From now on, we prove some results for 3-anti-circulant digraphs that belong to $\mathfrak{D}$.

Lemma 12. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. Let $v_1\leftrightarrow v_2$ be a digon in D. If $D\in \mathfrak{D}$ and there exists a vertex $v_3$ in $V\left(D\right)-\left\{v_1\mathrm{,}{v}_2\right\}$ such that $\left\{v_1\mathrm{,}{v}_2\right\}\to v_3$ and $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\cap S\ne \varnothing$, then D admits an S_BE-path partition.

Proof. The proof is divided into two cases depending on whether $v_3\in S$ or $v_3\notin S$. First, we prove the following claim.

Claim 1. If there exists a vertex $v_4\in V\left(D\right)-\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}$ such $v_4\to v_3$, then $D\left[\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\right]$ is a complete digraph.

Since $\left\{v_1\mathrm{,}{v}_2\right\}\to v_3$, $v_1\leftrightarrow v_2$ and D is 3-anti-circulant, it follows that $\left\{v_1\mathrm{,}{v}_2\right\}\to v_4$. Since $v_2\to v_4\leftarrow v_1\to v_3$, we conclude that $v_3\to v_2$, and hence, $v_2\leftrightarrow v_3$. Since $v_1\to v_4\leftarrow v_2\to v_3$, it follows that $v_3\to v_1$, and hence, $v_1\leftrightarrow v_3$. Thus $D\left[\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\right]$ is a complete digraph. This ends the proof of Claim 1.

Case 1. $v_3\notin S$. If $N^{-}\left(v_3\right)\ne \left\{v_1\mathrm{,}{v}_2\right\}$, then it follows by Claim 1 that $D\left[\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\right]$ is complete, and hence, the result follows by Lemma 11. So $N^{-}\left(v_3\right)=\left\{v_1\mathrm{,}{v}_2\right\}$. If $v_2\in S$ (resp., $v_1\in S$ ), then since $N^{-}\left(v_3\right)=\left\{v_1\mathrm{,}{v}_2\right\}$ and $v_3\notin S$, the result follows by Lemma 4 with $u_1=v_1$ (resp., $u_1=v_2$ ), $u_2=v_3$ and $P=v_2$ (resp., $P=v_1$ ).

Case 2. $v_3\in S$. Since $\left\{v_1\mathrm{,}{v}_2\right\}\to v_3$, $\left\{v_1\mathrm{,}{v}_2\right\}\cap S=\varnothing$. We may assume by Lemma 11 that $v_1\mapsto v_3$ and $v_2\mapsto v_3$. Thus it follows by Claim 1 that $N^{-}\left(v_3\right)=\left\{v_1\mathrm{,}{v}_2\right\}$. First, suppose that there exists a vertex $v_4$ in $N^{+}\left(v_2\right)-\left\{v_1\mathrm{,}{v}_3\right\}$. Since $v_1\to v_3\leftarrow v_2\to v_4$, it follows that $v_4\to v_1$. Since $v_4\to v_1\leftarrow v_2\to v_3$, we conclude that $v_3\to v_4$. Since $D\in \mathfrak{D}$, there exists at least one digon in $D\left[\left\{v_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$ ; otherwise, $D\left[\left\{v_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$ is an induced transitive triangle. Since $v_2\mapsto v_3$ and $N^{-}\left(v_3\right)=\left\{v_1\mathrm{,}{v}_2\right\}$, it follows that $v_2\leftrightarrow v_4$. Thus the result follows by Lemma 11 applied to $D\left[\left\{v_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$. So we may assume that $N^{+}\left(v_2\right)=\left\{v_1\mathrm{,}{v}_3\right\}$. Let $P=v_1$. Since $v_2\notin S$, $\left\{v_2\mathrm{,}{v}_3\right\}\cap V\left(P\right)=\varnothing$, $v_2\to v_1$, $v_1\to v_3$ and $N^{+}\left(v_2\right)\subseteq V\left(P\right)\cup \left\{v_3\right\}$, the result follows by Lemma 3 with $u_1=v_2$ and $u_2=v_3$. This finishes the proof.

By the principle of directional duality, we have the following result.

Lemma 13. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. Let $v_1\leftrightarrow v_2$ be a digon in D. If $D\in \mathfrak{D}$ and there exists a vertex $v_3$ in $V\left(D\right)-\left\{v_1\mathrm{,}{v}_2\right\}$ such that $v_3\to \left\{v_1\mathrm{,}{v}_2\right\}$ and $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\cap S\ne \varnothing$, then D admits an S_BE-path partition.

The following lemma states that we may assume that for every transitive triangle T in $D\in \mathfrak{D}$, $V\left(T\right)\cap S=\varnothing$.

Lemma 14. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. If $D\in \mathfrak{D}$ and D contains a transitive triangle T such that $V\left(T\right)\cap S\ne \varnothing$, then D admits an S_BE-path partition.

Proof. Let $V\left(T\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}$. Without loss of generality, assume that $v_1\to v_2$ and $\left\{v_1\mathrm{,}{v}_2\right\}\to v_3$. Since $D\in \mathfrak{D}$, there exists at least one digon in T; otherwise, T is an induced transitive triangle. If $v_1\leftrightarrow v_2$ (resp., $v_2\leftrightarrow v_3$ ), then the result follows by Lemma 12 (resp., Lemma 13). Thus $v_1\leftrightarrow v_3$. If $v_2\in S$, then the result follows by Lemma 11. So $\left\{v_1\mathrm{,}{v}_3\right\}\cap S\ne \varnothing$. Without loss of generality, assume that $v_3\in S$. We show next that $N^{+}\left(v_1\right)=\left\{v_2\mathrm{,}{v}_3\right\}$. Suppose that there exists a vertex $v_4$ in $N^{+}\left(v_1\right)-\left\{v_2\mathrm{,}{v}_3\right\}$. Since $v_2\to v_3\leftarrow v_1\to v_4$ and D is 3-anti-circulant, we conclude that $v_4\to v_2$. Also, since $v_4\to v_2\leftarrow v_1\to v_3$, it follows that $v_3\to v_4$. Thus the result follows by Lemma 12 applied to $D\left[\left\{v_1\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$. So we may assume that $N^{+}\left(v_1\right)=\left\{v_2\mathrm{,}{v}_3\right\}$. Let $P=v_2$. Since $v_1\notin S$, $\left\{v_1\mathrm{,}{v}_3\right\}\cap V\left(P\right)=\varnothing$, $v_1\to v_2$, $v_2\to v_3$ and $N^{+}\left(v_1\right)\subseteq V\left(P\right)\cup \left\{v_3\right\}$, the result follows by Lemma 3 with $u_1=v_1$ and $u_2=v_3$. This finishes the proof.

The next lemma states that we may assume that $B^{-}\cup B^{\pm }\Rightarrow B^{+}$.

Lemma 15. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. If $D\in \mathfrak{D}$ and there are vertices $v_1\in B^{+}$ and $v_2\in B^{-}\cup B^{\pm }$ such that $v_1\to v_2$, then D admits an S_BE-path partition.

Proof. By definition of $B^{+}$, there exists a vertex $y_1$ in S such that $v_1\to y_1$. By definition of $B^{\pm }$ and $B^{-}$, there exists a vertex $y_2$ in S such that $y_2\to v_2$. Towards a contradiction, suppose that $y_1\ne y_2$. Since $y_2\to v_2\leftarrow v_1\to y_1$ and D is 3-anti-circulant, it follows that $y_2\to y_1$, a contradiction because S is stable. So $y_1=y_2$, and hence, the result follows by Lemma 14 applied to $D\left[\left\{v_1\mathrm{,}{v}_2\mathrm{,}{y}_1\right\}\right]$.

By the principle of directional duality, we have the following result.

Lemma 16. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. If $D\in \mathfrak{D}$ and there are $v_1\in B^{+}\cup B^{\pm }$ and $v_2\in B^{-}$ such that $v_1\to v_2$, then D admits an S_BE-path partition.

We show next that if $D\in \mathfrak{D}$, then we may assume that $B^{\pm }$ is a stable set.

Lemma 17. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. If $D\in \mathfrak{D}$ and $B^{\pm }$ is not stable, then D admits an S_BE-path partition.

Proof. Let $v_1\mathrm{,}{v}_2$ be adjacent vertices in $B^{\pm }$. Without loss of generality, assume that $v_1\to v_2$. By definition of $B^{\pm }$, there are vertices $y_1\mathrm{,}{y}_2$ in S such that $v_1\to y_1$ and $y_2\to v_2$. Since S is stable and D is 3-anti-circulant, it follows that $y_1=y_2$, and hence, the result follows by Lemma 14 applied to $D\left[\left\{v_1\mathrm{,}{v}_2\mathrm{,}{y}_1\right\}\right]$.

The next lemma states that if D contains an anti-P₄ disjoint from S, then D admits an S_BE-path partition.

Lemma 18. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. If $D\in \mathfrak{D}$ and D contains an anti-P₄ disjoint from S, then D admits an S_BE-path partition.

Proof. Let $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\subseteq V\left(D\right)$ be an anti-P₄ in D such that $v_1\to v_2\leftarrow v_3\to v_4$. Since D is 3-anti-circulant, we conclude that $v_4\to v_1$. We show next that $v_2\in B^{+}$ and $v_3\in B^{-}$. Note that by the principle of directional duality, it suffices to show that $v_3\in B^{-}$. Moreover, we may assume by Lemma 15 that $B^{-}\cup B^{\pm }\Rightarrow B^{+}$. Towards a contradiction, suppose that $v_3\notin B^{-}$. Since $v_3\notin S$, it follows that $v_3\in B^{+}\cup B^{\pm }$. If $v_3\in B^{+}$, then since $v_3\to \left\{v_2\mathrm{,}{v}_4\right\}$ and $B^{-}\cup B^{\pm }\Rightarrow B^{+}$, we conclude that $\left\{v_2\mathrm{,}{v}_4\right\}\subset B^{+}$. Since $v_4\in B^{+}$, it follows that $v_1\in B^{+}$, and hence, $\left|N^{-}\left(v_2\right)\cap B^{+}\right|>1$, a contradiction by Lemma 9. If $v_3\in B^{\pm }$, then since $v_3\to v_4$, it follows by Lemma 17 that $v_4\notin B^{\pm }$. By Lemma 16, $v_4\notin B^{-}$. So $v_4\in B^{+}$. Since $v_4\in B^{+}$ and $B^{-}\cup B^{\pm }\Rightarrow B^{+}$, it follows that $v_1\in B^{+}$. By definition of $B^{\pm }$, there exists a vertex y in S such that $v_3\to y$. Since $v_1\to v_2\leftarrow v_3\to y$, we conclude that $y\to v_1$, a contradiction because $v_1\in B^{+}$. Thus $v_3\in B^{-}$ and $v_2\in B^{+}$.

Now, let $P_1=v_4{v}_1{v}_2$ and let $P_2=v_3{v}_4{v}_1$. Towards a contradiction, suppose that $N^{+}\left(v_3\right)\cancel{\subseteq }V\left(P_1\right)$ and $N^{-}\left(v_2\right)\cancel{\subseteq }V\left(P_2\right)$. So let $w_1\mathrm{,}{w}_2$ vertices such that $w_1$ in $N^{-}\left(v_2\right)-V\left(P_2\right)$ and $w_2$ in $N^{+}\left(v_3\right)-V\left(P_1\right)$. First, suppose that $w_1=w_2$. Since $D\in \mathfrak{D}$, there exists at least one digon in $D\left[\left\{v_2\mathrm{,}{v}_3\mathrm{,}{w}_1\right\}\right]$ ; otherwise, $D\left[\left\{v_2\mathrm{,}{v}_3\mathrm{,}{w}_1\right\}\right]$ is an induced transitive triangle. Since $v_2\in B^{+}$ and $B^{-}\cup B^{\pm }\Rightarrow B^{+}$, we conclude that $w_1\leftrightarrow v_3$, and since $v_3\in B^{-}$, the result follows by Lemma 16. So we may assume that $w_1\ne w_2$ (see Figure 5(a)).

Figure 5. Illustration for the proof of Lemma 18.

Since $w_1\to v_2\leftarrow v_3\to \left\{w_2\mathrm{,}{v}_4\right\}$, we conclude that $\left\{w_2\mathrm{,}{v}_4\right\}\to w_1$. Since $v_1\to v_2\leftarrow v_3\to w_2$, $w_2\to v_1$. Also, since $v_4\to w_1\leftarrow w_2\to v_1$, we conclude that $v_1\to v_4$, and hence, $v_1\leftrightarrow v_4$ (see Figure 5(b)). Since $v_3\to v_4\leftarrow v_1\to v_2$, it follows that $v_2\to v_3$, a contradiction because $v_2\in B^{+}$, $v_3\in B^{-}$ and $B^{-}\cup B^{\pm }\Rightarrow B^{+}$. Thus $N^{+}\left(v_3\right)\subseteq V\left(P_1\right)$ or $N^{-}\left(v_2\right)\subseteq V\left(P_2\right)$. Since $\left\{v_1,v_2,v_3,v_4\right\}\cap S=\varnothing$, the result follows by Lemma 1 with $u=v_3$ or by Lemma 2 with $u=v_2$.

In the next lemmas, we show that if $D\in \mathfrak{D}$, then $B^{+}$ and $B^{-}$ are stable. To do this, we show that there exists no arc $v_1{v}_2$ in D such that $v_1\in B^{+}\cup B^{-}$ and $v_2\in B^{\pm }$.

Lemma 19. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set in D. If $D\in \mathfrak{D}$ and there are adjacent vertices $v_1\mathrm{,}{v}_2$ in $V\left(D\right)$ such that $v_1\in B^{+}\cup B^{-}$ and $v_2\in B^{\pm }$, then D admits an S_BE-path partition.

Proof. By the principle of directional duality, we may assume that $v_1\in B^{+}$. Also, we may assume by Lemma 15 that $B^{-}\cup B^{\pm }\Rightarrow B^{+}$. So $v_2\mapsto v_1$. By definition of $B^{+}$, there exists a vertex $y_1$ in S such that $v_1\mapsto y_1$. By definition of $B^{\pm }$, there exists a vertex $y_2$ in S such that $v_2\to y_2$.

Claim 1. $N^{-}\left(v_1\right)\cap B^{+}=\varnothing$ .

Towards a contradiction, suppose that there exists $v_3\in B^{+}$ such that $v_3\to v_1$. Since $v_3\to v_1\leftarrow v_2\to y_2$ and D is 3-anti-circulant, it follows that $y_2\to v_3$, a contradiction by definition of $B^{+}$. Thus $N^{-}\left(v_1\right)\cap B^{+}=\varnothing$. This finishes the proof of Claim 1.

If $N^{-}\left(v_1\right)=\left\{v_2\right\}$, then since $\left\{v_1,v_2\right\}\cap S=\varnothing$, the result follows by Lemma 2 with $P=v_2$ and $u=v_1$. So there exists a vertex $v_3$ in $N^{-}\left(v_1\right)-v_2$. By definition of $B^{+}$, $v_3\notin S$. By Claim 1, $v_3\in B^{\pm }\cup B^{-}$. The rest of proof is divided into two cases depending on whether $v_3\in B^{\pm }$ or $v_3\in B^{-}$.

Case 1. $v_3\in B^{\pm }$. Recall that $v_2\to y_2$ with $y_2\in S$. Since $v_2\in B^{\pm }$, we may assume by Lemma 17 that $v_2$ and $v_3$ are non-adjacent. By definition of $B^{\pm }$, there exists a vertex $y_3$ in S such that $v_3\to y_3$. Towards a contradiction, suppose that $y_3=y_2$. Since $v_3\to y_2\leftarrow v_2\to v_1$, we conclude that $v_1\to v_3$, a contradiction because $B^{-}\cup B^{\pm }\Rightarrow B^{+}$. So $y_3\ne y_2$. Since $v_3\to v_1\leftarrow v_2\to y_2$, $y_2\to v_3$. Also, since $v_2\to v_1\leftarrow v_3\to y_3$, $y_3\to v_2$ (see Figure 6).

Figure 6. Illustration for the proof of Lemma 19.

Claim 2. $N^{-}\left(\left\{y_2\mathrm{,}{y}_3\right\}\right)\cap \left(B^{-}\cup B^{\pm }\right)=\left\{v_2\mathrm{,}{v}_3\right\}$ .

By definition of $B^{-}$, $N^{-}\left(\left\{y_2,y_3\right\}\right)\cap B^{-}=\varnothing$. Towards a contradiction, suppose that there exists a vertex $v_4\in B^{\pm }-\left\{v_2\mathrm{,}{v}_3\right\}$ such that $v_4\to y_i$ for some $i\in \left\{\mathrm{2,3}\right\}$. Since $v_4\to y_i\leftarrow v_i\to v_1$, we conclude that $v_1\to v_4$, a contradiction because $B^{-}\cup B^{\pm }\Rightarrow B^{+}$. So $N^{-}\left(\left\{y_2\mathrm{,}{y}_3\right\}\right)\cap \left(B^{-}\cup B^{\pm }\right)=\left\{v_2\mathrm{,}{v}_3\right\}$. This ends the proof of Claim 2.

Claim 3. $N^{+}\left(\left\{v_2,v_3\right\}\right)-S=\left\{v_1\right\}$ .

Towards a contradiction, suppose that there exists $v_4\in V\left(D\right)-\left(S\cup \left\{v_1\right\}\right)$ such that $v_i\to v_4$ for some $i\in \left\{\mathrm{2,3}\right\}$. Then, $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}$ is an anti-P₄ disjoint from S, and hence, the result follows by Lemma 18. So we may assume that $N^{+}\left(\left\{v_2,v_3\right\}\right)-S=\left\{v_1\right\}$. This finishes the proof of Claim 3.

Claim 4. If there exists a vertex $v_4$ in $V\left(D\right)-\left(S\cup \left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\right)$ such that $v_4\to v_i$ for some $i\in \left\{\mathrm{2,3}\right\}$, then $v_4\in B^{-}$ and $N^{+}\left(v_4\right)=\left\{v_2,v_3\right\}$ . Moreover, $N^{-}\left(\left\{v_2,v_3\right\}\right)-S=\left\{v_4\right\}$ .

Without loss of generality, assume that $v_4\to v_3$. Since $B^{-}\cup B^{\pm }\Rightarrow B^{+}$, $v_4\notin B^{+}$. Since $\left\{v_2\mathrm{,}{v}_3\right\}\subseteq B^{\pm }$, it follows by Lemma 17 that $v_4\in B^{-}$ (see Figure 7).

Figure 7. Illustration for the proof of Lemma 19.

By definition of $B^{-}$, $N^{+}\left(v_4\right)\cap S=\varnothing$. Now, we show that $N^{+}\left(v_4\right)\subseteq \left\{v_2\mathrm{,}{v}_3\right\}$. First, suppose that $v_4\to v_1$. Since $D\in \mathfrak{D}$, there exists at least one digon in $D\left[\left\{v_1\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$ ; otherwise, $D\left[\left\{v_1\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\right]$ is an induced transitive triangle. Since $B^{-}\cup B^{\pm }\Rightarrow B^{+}$, $v_3\leftrightarrow v_4$ which contradicts Claim 3. So $v_1\notin N^{+}\left(v_4\right)$. Now, let $v_5$ be a vertex in $N^{+}\left(v_4\right)-\left\{v_2\mathrm{,}{v}_3\right\}$. By definition of $B^{-}$ and since $v_4\in B^{-}$, it follows that $v_5\notin S$. Since $y_2\to v_3\leftarrow v_4\to v_5$, we conclude that $v_5\to y_2$. Since $v_5\to y_2\leftarrow v_2\to v_1$, we conclude that $v_1\to v_5$. Thus since $\left\{v_1,v_3,v_4,v_5\right\}\cap S=\varnothing$ and $v_1\to v_5\leftarrow v_4\to v_3$, the result follows by Lemma 18. So $N^{+}\left(v_4\right)\subseteq \left\{v_2\mathrm{,}{v}_3\right\}$. If $N^{+}\left(v_4\right)=\left\{v_i\right\}$ for some $i\in \left\{\mathrm{2,3}\right\}$, then it follows by Lemma 1 with $P=v_i$ and $u=v_4$ that D admits an S_BE-path partition. Thus $N^{+}\left(v_4\right)=\left\{v_2\mathrm{,}{v}_3\right\}$. Moreover, if $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S\supset \left\{v_4\right\}$, then D contains an anti-P₄ disjoint from S, and hence, the result follows by Lemma 18. Thus $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S=\left\{v_4\right\}$. This ends the proof of Claim 4.

Claim 5. If $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S\ne \varnothing$, then $N^{-}\left(v_1\right)=\left\{v_2\mathrm{,}{v}_3\right\}$ .

Let $v_4$ be a vertex in $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S$. It follows by Claim 4 that $N^{+}\left(v_4\right)=\left\{v_2\mathrm{,}{v}_3\right\}$ and $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S=\left\{v_4\right\}$. Suppose that there exists a vertex $v_5$ in $N^{-}\left(v_1\right)-\left\{v_2\mathrm{,}{v}_3\right\}$. By definition of $B^{+}$, $v_5\notin S$. Since $v_5\to v_1\leftarrow v_2\to y_2$, $y_2\to v_5$. Also, since $v_4\to v_3\leftarrow y_2\to v_5$, $v_5\to v_4$. Since $\left\{v_1,v_3,v_4,v_5\right\}\cap S=\varnothing$ and $v_3\to v_1\leftarrow v_5\to v_4$, it follows by Lemma 18 that D admits an S_BE-path partition. So we may assume that $N^{-}\left(v_1\right)=\left\{v_2\mathrm{,}{v}_3\right\}$. This ends the proof of Claim 5.

The rest of proof is divided into two subcases depending on whether $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S\ne \varnothing$ or $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S=\varnothing$.

Subcase 1. $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S\ne \varnothing$. Let $v_4$ be a vertex in $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S$. It follows by Claim 4 that $N^{+}\left(v_4\right)=\left\{v_2\mathrm{,}{v}_3\right\}$ and $N^{-}\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)-S=\left\{v_4\right\}$. By Claim 5, $N^{-}\left(v_1\right)=\left\{v_2\mathrm{,}{v}_3\right\}$. Let $D^{\prime }=D-\left\{v_2,v_3\right\}$. Note that $v_1$ is a source and $v_4$ is a sink in $D^{\prime }$. Since $\left\{v_2,v_3\right\}\cap S=\varnothing$, S is a maximum stable set in $D^{\prime }$. By hypothesis, $D^{\prime }$ is BE-perfect. Let ${\mathcal{P}}^{\prime }$ be an S_BE-path partition of $D^{\prime }$. Let $P_1\mathrm{,}{P}_2$ be distinct paths in ${\mathcal{P}}^{\prime }$ such that $P_1$ starts at $v_1$ and $P_2$ ends at $v_4$. Thus the collection $\left\{{\mathcal{P}}^{\prime }-\left\{P_1\mathrm{,}{P}_2\right\}\right\}\cup \left\{v_2{P}_1\mathrm{,}{P}_2{v}_3\right\}$ is an S_BE-path partition of D.

Subcase 2. $N^{-}\left(\left\{v_2,v_3\right\}\right)-S=\varnothing$. By Claim 3, $N\left(\left\{v_2,v_3\right\}\right)-S=\left\{v_1\right\}$. Let

$D^{\prime }=D-v_1$. Since $v_1\notin S$, S is a maximum stable set in $D^{\prime }$. Let ${\mathcal{P}}^{\prime }$ be an S_BE-path partition of $D^{\prime }$. Let $P_1$ be a path in ${\mathcal{P}}^{\prime }$ such that $v_2\in V\left(P_1\right)$ and let $P_2$ be a path in ${\mathcal{P}}^{\prime }$ such that $v_3\in V\left(P_2\right)$. In $D^{\prime }$, $N\left(\left\{v_2\mathrm{,}{v}_3\right\}\right)\subset S$. So it follows that both $P_1$ and $P_2$ have length one. If $P_1$ ends at $v_2$ or $P_2$ ends at $v_3$, then since $v_2\to v_1$ and $v_3\to v_1$, the collection $\left({\mathcal{P}}^{\prime }-\left\{P_1\right\}\right)\cup \left\{P_1{v}_1\right\}$ or $\left({\mathcal{P}}^{\prime }-\left\{P_2\right\}\right)\cup \left\{P_2{v}_1\right\}$ is an S_BE-path partition of D. Thus $P_1=v_2{w}_1$ and $P_2=v_3{w}_2$ with $w_1\mathrm{,}{w}_2\in S$. Since $\left\{v_2\mathrm{,}{v}_3\right\}\to v_1$, $v_2\to w_1$ and $v_3\to w_2$, we conclude that $w_1\to v_3$ and $w_2\to v_2$. Thus the collection $\left({\mathcal{P}}^{\prime }-\left\{P_1\mathrm{,}{P}_2\right\}\right)\cup \left\{w_2{v}_2{v}_1\mathrm{,}{w}_1{v}_2\right\}$ is an S_BE-path partition of D.

Case 2. $v_3\in B^{-}$. By definition of $B^{-}$, $N^{+}\left(v_3\right)\cap S=\varnothing$. If there exists a vertex $v_4$ in $N^{+}\left(v_3\right)-\left\{v_1\mathrm{,}{v}_2\right\}$, then since $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}\cap S=\varnothing$ and $v_2\to v_1\leftarrow v_3\to v_4$, the result follows by Lemma 18. Thus $N^{+}\left(v_3\right)\subseteq \left\{v_1\mathrm{,}{v}_2\right\}$, and hence, since $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\cap S=\varnothing$, the result follows by Lemma 1 with $P=v_2{v}_1$ and $u=v_3$. This ends the proof.

Now, we show that if $D\in \mathfrak{D}$, then we may assume that there exists no arc $v_1{v}_2$ in D such that $v_1\in B^{+}$ and $v_2\in B^{-}$.

Lemma 20. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set of D. If $D\in \mathfrak{D}$ and there are adjacent vertices $v_1\mathrm{,}{v}_2$ in $V\left(D\right)$ such that $v_1\in B^{+}$ and $v_2\in B^{-}$, then D admits an S_BE-path partition.

Proof. We may assume by Lemma 15 that $B^{-}\cup B^{\pm }\Rightarrow B^{+}$. So $v_2\mapsto v_1$. If $N^{-}\left(v_1\right)=\left\{v_2\right\}$, then since $\left\{v_1,v_2\right\}\cap S=\varnothing$, the result follows by Lemma 2 with $P=v_2$ and $u=v_1$. So there exists a vertex $v_3$ in $N^{-}\left(v_1\right)-v_2$. Since $v_1\in B^{+}$, $v_3\notin S$. Since $v_2\in B^{-}$, $N^{+}\left(v_2\right)\cap S=\varnothing$. If there exists a vertex $v_4$ in $N^{+}\left(v_2\right)-\left\{v_1\mathrm{,}{v}_3\right\}$, then since $\left\{v_1,v_2,v_3,v_4\right\}\cap S=\varnothing$ and $v_3\to v_1\leftarrow v_2\to v_4$, the result follows by Lemma 18. So we may assume that $N^{+}\left(v_2\right)\subseteq \left\{v_1\mathrm{,}{v}_3\right\}$. Since $\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}\cap S=\varnothing$, it follows by Lemma 1 with $P=v_3{v}_1$ and $u=v_2$ that D admits an S_BE-path partition. This finishes the proof.

We show next that we may assume that $B^{+}\cup B^{-}$ is a stable set.

Lemma 21. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the BE-property. Let S be a maximum stable set of D. If $D\in \mathfrak{D}$ and $B^{+}\cup B^{-}$ is not a stable set, then D admits an S_BE-path partition.

Proof. If there are adjacent vertices $v_1\mathrm{,}{v}_2$ in $V\left(D\right)$ such that $v_1\in B^{+}$ and $v_2\in B^{-}$, then the result follows by Lemma 20. Let $v_1{v}_2$ be an arc in $D\left[B^{+}\cup B^{-}\right]$. By the principle of directional duality, we may assume that $\left\{v_1\mathrm{,}{v}_2\right\}\subseteq B^{+}$. Towards a contradiction, suppose that $N^{-}\left(v_2\right)\supset \left\{v_1\right\}$. Let $v_3$ be a vertex in $N^{-}\left(v_2\right)-v_1$. By definition of $B^{+}$, $v_3\notin S$. Moreover, we may assume by Lemmas 20 and 19 that $v_3\in B^{+}$. By definition of $B^{+}$, let y be a vertex in S such that $v_1\to y$. Since $v_3\to v_2\leftarrow v_1\to y$, we conclude that $y\to v_3$, a contradiction by definition of $B^{+}$. Thus $N^{-}\left(v_2\right)=\left\{v_1\right\}$. Since $\left\{v_1\mathrm{,}{v}_2\right\}\cap S=\varnothing$, it follows by Lemma 2 with $P=v_1$ and $u=v_2$ that D admits an S_BE-path partition.

Finally, we are ready for the main result of this subsection.

Theorem 2 Let D be a 3-anti-circulant digraph. If $D\in \mathfrak{D}$, then D is BE-diperfect.

Proof. Let S be a maximum stable set of D. Since every induced subdigraph of D is also a 3-anti-circulant digraph, it suffices to show that D satisfies the BE-property. Towards a contradiction, suppose the opposite and let D be a counterexample with the smallest number of vertices. Note that if $D^{\prime }$ is a proper induced subdigraph of D, then $D^{\prime }$ is a 3-anti-circulant digraph, and hence, by the minimality of D, it follows that $D^{\prime }$ satisfies the BE-property. Thus D does not satisfy the BE-property. It follows by Lemmas 17 and 21 that both $B^{\pm }$ and $B^{+}\cup B^{-}$ are stable. Thus it follows by Lemmas 19 and 20 that $B^{+}\cup B^{-}\cup B^{\pm }$ is stable. Since S is a maximum stable set of D, $\left|S\right|\ge \left|B^{+}\cup B^{-}\cup B^{\pm }\right|$. Thus we conclude by Lemma 10 that D satisfies the BE-property, a contradiction. This ends the proof.

4.2. Berge’s Conjecture

In this subsection, we verify Conjecture 1 for 3-anti-circulant digraphs. Recall that every 3-anti-circulant digraph belongs to $\mathfrak{B}$. The proof is divided into two cases depending on whether D contains an induced transitive triangle or not.

Lemma 22. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the α-property. If D contains an induced transitive triangle T, then D satisfies the α-property.

Proof. Let S be a maximum stable set in D. Let $V\left(T\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}$. Without loss of generality, assume that $\left\{v_1\mathrm{,}{v}_2\right\}\mapsto v_3$ and $v_1\mapsto v_2$. First, we prove some claims.

Claim 1. $\left|N^{-}\left(v_3\right)\right|\le 3$ . Moreover, if there exists $v_4\in N^{-}\left(v_3\right)-\left\{v_1\mathrm{,}{v}_2\right\}$, then $v_4\to v_1$ and $v_2\to v_4$ .

Towards a contradiction, suppose that there are distinct vertices $v_4\mathrm{,}{v}_5$ in $N^{-}\left(v_3\right)-\left\{v_1\mathrm{,}{v}_2\right\}$. Since $\left\{v_4\mathrm{,}{v}_5\right\}\to v_3\leftarrow v_1\to v_2$ and D is 3-anti-circulant, it follows that $v_2\to \left\{v_4\mathrm{,}{v}_5\right\}$. Since $v_1\to v_3\leftarrow v_2\to \left\{v_4\mathrm{,}{v}_5\right\}$, we conclude that $\left\{v_4\mathrm{,}{v}_5\right\}\to v_1$. Also, since $v_5\to v_3\leftarrow v_2\to v_4$, it follows that $v_4\to v_5$. Now, since $v_2\to v_5\leftarrow v_4\to v_3$, it follows that $v_3\to v_2$, and hence, $v_2\leftrightarrow v_3$, a contradiction because $v_2\mapsto v_3$. Thus $\left|N^{-}\left(v_3\right)\right|\le 3$. Moreover, note that if there exists $v_4\in N^{-}\left(v_3\right)-\left\{v_1\mathrm{,}{v}_2\right\}$, then $v_4\to v_1$ and $v_2\to v_4$. This ends the proof of Claim 1.

Claim 2. $\left\{v_1\mathrm{,}{v}_2\right\}\cap S\ne \varnothing$ .

Suppose that $\left\{v_1,v_2\right\}\cap S=\varnothing$. First, suppose that there exists a vertex $v_4$ in $N^{-}\left(v_3\right)-\left\{v_1\mathrm{,}{v}_2\right\}$. By Claim 1, it follows that $N^{-}\left(v_3\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_4\right\}$, $v_4\to v_1$ and $v_2\to v_4$. Let $D^{\prime }=D-\left\{v_1\mathrm{,}{v}_2\right\}$. Since $\left\{v_1,v_2\right\}\cap S=\varnothing$, S is a maximum stable set in $D^{\prime }$. By hypothesis, $D^{\prime }$ is α-diperfect. Let ${\mathcal{P}}^{\prime }$ be an S-path partition of $D^{\prime }$. Let P be a path in ${\mathcal{P}}^{\prime }$ such that $v_3\in V\left(P\right)$. Since $N^{-}\left(v_3\right)=\left\{v_1,v_2,v_4\right\}$, it follows that P starts at $v_3$ or $v_4{v}_3$ is an arc of P. If P starts at $v_3$, then since $v_1\to v_2$ and $v_2\to v_3$, the collection $\left({\mathcal{P}}^{\prime }-\left\{P\right\}\right)\cup \left\{v_1{v}_{2}P\right\}$ is an S-path partition of D (note that if $N^{-}\left(v_3\right)=\left\{v_1,v_2\right\}$, then the result follows by previous argument). Thus $v_4{v}_3$ is an arc of P. Let $w_1$ and $w_p$ be the endvertices of P. Let $P_1=w_{1}P{v}_4$ and $P_2=v_{3}P{w}_p$ be the subpaths of P. Since $v_4\to v_1$, $v_1\to v_2$ and $v_2\to v_3$, the collection $\left({\mathcal{P}}^{\prime }-\left\{P\right\}\right)\cup \left\{P_1{v}_1{v}_2{P}_2\right\}$ is an S-path partition of D. So we may assume that $\left\{v_1\mathrm{,}{v}_2\right\}\cap S\ne \varnothing$. This finishes the proof of Claim 2.

Claim 3. $\left\{v_2\mathrm{,}{v}_3\right\}\cap S\ne \varnothing$ .

By the principle of directional duality, the result follows by Claim 2. This ends the proof of Claim 3.

By Claims 2 and 3, it follows that $v_2\in S$. First, suppose that there exists a vertex $v_4$ in $N^{-}\left(v_3\right)-\left\{v_1\mathrm{,}{v}_2\right\}$. By Claim 1, it follows that $N^{-}\left(v_3\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}{v}_4\right\}$, $v_4\to v_1$ and $v_2\to v_4$. Let $P=v_2{v}_4{v}_1$ and $u=v_3$. Since $\left(V\left(P\right)-v_2\right)\cap S=\varnothing$, $v_1\to u$ and $N^{-}\left(u\right)\subseteq V\left(P\right)$, it follows by Lemma 7 that D admits an S-path partition. So we may assume that $N^{-}\left(v_3\right)=\left\{v_1\mathrm{,}{v}_2\right\}$.

Now, suppose that $N^{+}\left(v_2\right)=\left\{v_3\right\}$. Since $v_3\notin S$, the result follows by Lemma 66. So we may assume that there exists a vertex w in $N^{+}\left(v_2\right)-\left\{v_1\mathrm{,}{v}_3\right\}$. Since $v_1\to v_3\leftarrow v_2\to w$, we conclude that $w\to v_1$. Let $P=v_{2}w{v}_1$ and let $u=v_3$. Since $\left(V\left(P\right)-v_2\right)\cap S=\varnothing$, $v_1\to u$ and $N^{-}\left(u\right)\subset V\left(P\right)$, the result follows by Lemma 7. This finishes the proof.

We show next that if D contains no induced transitive triangle, then D satisfies the α-property.

Lemma 23. Let D be a 3-anti-circulant digraph such that every proper induced subdigraph of D satisfies the α-property. If D contains no induced transitive triangle, then D satisfies the α-property.

Proof. Since every blocking odd cycle of length at least five contains an induced anti-P₄ and D is 3-anti-circulant, it follows that D contains no blocking odd cycle of length at least five. Moreover, D contains no induced transitive triangle, and this implies that D belongs to $\mathfrak{D}$. So by Theorem 2 D satisfies the BE-property, and hence, the α-property.

Now, we prove the main result of this subsection.

Theorem 3. Let D be a 3-anti-circulant digraph. Then, D is α-diperfect.

Proof. Since every induced subdigraph of D is also a 3-anti-circulant digraph, it suffices to show that D satisfies the α-property. If D contains an induced transitive triangle, then the result follows by Lemma 22. Thus D contains no induced transitive triangle, and hence, the result follows by Lemma 23. This ends the proof.

5. Concluding Remarks

In this paper, we presented two conjectures related to maximum stable set and path partition in digraphs. We verified both Conjectures 1 and 2 for 3-anti-circulant digraphs. These digraphs do not contain anti-P₄ as an induced subdigraph. We believe that studying the structure of these digraphs should help towards obtaining a proof of both conjectures in the general case.

Furthermore, an interesting and natural continuation in study of the structure of these digraphs is to analyze digraphs which for every anti-P₄ $v_1\to v_2\leftarrow v_3\to v_4$, it follows that $v_1$ and $v_4$ are adjacent. Here, we believe this could be a challenging problem.

Acknowledgements

We appreciate suggestions given by referees that have improved overall presentation of the paper. Moreover, the second author was supported by CNPq Proc. 303766/2018-2, CNPq Proc 425340/2016-3 and FAPESP Proc. 2015/11937-9.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bang-Jensen, J. and Gutin, G.Z. (2008) Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Springer, London. https://doi.org/10.1007/978-1-84800-998-1
[2]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory, Volume 244 of Graduate Texts in Mathematics. Springer London, New York. https://doi.org/10.1007/978-1-84628-970-5
[3]	Berge, C. (1961) Färbung von graphen, deren sämtliche bzw. deren ungerade kreise starr sind. Wissenschaftliche Zeitschrift.
[4]	Chudnovsky, M., Robertson, N., Seymour, P. and Thomas, R. (2006) The Strong Perfect Graph Theorem. Annals of Mathematics, 51-229. https://doi.org/10.4007/annals.2006.164.51
[5]	Berge, C. (1981) Diperfect Graphs. 1-8. https://doi.org/10.1007/BFb0092250
[6]	Hartman, I.B.-A. (2006) Berge’s Conjecture on Directed Path Partitions—A Survey. Discrete Mathematics, 306, 2498-2514. https://doi.org/10.1016/j.disc.2005.12.039
[7]	Sambinelli, M. and Lee, O. (2018) Partition Problems in Graphs and Digraphs. Ph.D. Thesis, University of Campinas, Campinas.
[8]	Sambinelli, M., da Silva, C.N. and Lee, O. (2022) α-Diperfect Digraphs. Discrete Mathematics, 345, 112759. https://doi.org/10.1016/j.disc.2021.112759
[9]	Freitas, L.I.B. and Lee, O. (2021) Some Results on Berge’s Conjecture and Begin-End Conjecture. arXiv: 2111.12168.
[10]	Wang, R.X. (2014) Cycles in 3-Anti-Circulant Digraphs. Australasian Journal of Combinatorics, 60, 158-168.