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
and arc set
. We only consider finite digraphs without loops and multiple arcs. Given two vertices u and v of
, we denote an arc from u to v by uv. In this case, we say that u dominates v, and we denote this by
. We say that u and v are adjacent if
or
; otherwise, we say that u and v are non-adjacent. If
and
, then we denote this by
; we also say that
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
and
; moreover, if every arc of
with both vertices in
is in
, then we say that H is induced by
, and we write
. 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
and
. The underlying graph of D, denoted by
, is the simple graph defined by
and
and v are adjacent in
.
We say that a vertex u is an in-neighbor (resp., out-neighbor) of a vertex v if
(resp.,
). Let X be a subset of
. We denote by
(resp.,
) the set of vertices in
that are in-neighbors (resp., out-neighbors) of some vertex of X. We define the neighborhood of X as
; when
, we write
,
and
. We say that v is a source if
and a sink if
.
For disjoint subsets X and Y of
(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,
means that every vertex of X dominates every vertex of Y,
means that there exists no arc from Y to X and
means that both
and
hold. When
or
, we write
and
.
A path P in a digraph D is a sequence of distinct vertices
such that for all
in P,
for
. Whenever it is appropriate, we treat P as being the subdigraph of D with vertex set
and arc set
. We say that P starts at
and ends at
. We also say that
are endvertices of P and
is the initial and
is the final of P; to emphasize this fact we may write P as
. Also, whenever it is convenient, we may omit the initial or the final in the notation as
or
. We denote by
a subpath of P where
. We define the length of P as
. We denote by
the class of isomorphism of a path of length
. If
, then we say that P is a Hamilton path of D, and in this case, we say that D is traceable. Let
be paths in D. If P ends at some vertex v and Q starts at some vertex u such that
, 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
such that
is a path,
and
. Whenever it is convenient, we also treat C as the subdigraph of D with vertex set
and arc set
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
the class of isomorphism of a cycle of length k. If
, 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
is a cycle in
. 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
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
. A collection of disjoint paths
of D is a path partition of
, if every vertex in
belongs to exactly one path of
. Let S be a stable set of D. We say that S and
are orthogonal if
for every
.
Let G be a connected graph. A clique is a set of pairwise adjacent vertices of G. The clique number of G, denoted by
, is the size of maximum clique of G. We say that a vertex set
is a vertex cut if
is a disconnected graph. If
is a complete graph, then we say that B is a clique cut. A (proper) coloring of G is a partition of
into stable sets
. The chromatic number of G, denoted by
, 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
holds. Moreover, we say that a digraph D is diperfect if
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
such that S and
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)
is a non-oriented odd cycle, where
and 2) each of the vertices
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
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
. In 1982, Berge [5] verified Conjecture 1 for diperfect digraphs and for symmetric digraphs (digraphs such that if
, then
). 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
is an SBE-path partition of D if 1)
and S are orthogonal and 2) every vertex of S is the initial or the final of a path in
. We say that D satisfies the BE-property if for every maximum stable set of D there exists an SBE-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)
is a non-oriented odd cycle, where
and 2)
is a source and
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
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
. 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
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 SBE-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
be a path of D such that
. If there exists a vertex u in
such that
,
and
, then D admits an SBE-path partition (resp., S-path partition).
Proof. Let i be the minimum in
such that
. Let
. Note that
. Let
. Note that u is a sink in
. Since
, S is a maximum stable set in
. By hypothesis,
is BE-perfect. Let
be an SBE-path partition of
. Let R be a path in
such that
. Since u is a sink in
, it follows that R ends at u. Since
, the collection
is an SBE-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
be a path of D such that
. If there exists a vertex u in
such that
,
and
, then D admits an SBE-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
be a path of D such that
. If there exists an arc
in
such that
,
,
and
, then D admits an SBE-path partition (resp., S-path partition).
Proof. Let i be the minimum in
such that
. Let
. Note that
. Let
. Since
, S is a maximum stable set in
. By hypothesis,
is BE-diperfect. Let
be an SBE-path partition of
. Let R be a path in
such that
. If R ends at
, then since
, it follows that the collection
is an SBE-path partition of D. So we may assume that P does not end at
. Since
, it follows that
is an arc in R. Let
and
be the endvertices of R. Let
and let
. Since
and
, the collection
is an SBE-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
be a path of D such that
. If there exists an arc
in
such that
,
,
and
, then D admits an SBE-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 SBE-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
admits a partition
such that
,
is hamiltonian,
and
, then D admits an SBE-path partition (resp., S-path partition).
Proof. Let
. Let
be a Hamilton cycle in
. Let B be a subset of
with cardinality
(note that B exists because
and
). Without loss of generality, we may assume that
is the vertex in
. Let
. Since
, S is maximum in
. By hypothesis,
is BE-diperfect. Let
be an SBE-path partition of
. Let P be a path in
such that
. First, suppose that P does not start at
. Let w be the vertex in P that immediately precedes
. Let
and let
. Since
and
, it follows that w in
. Let
. Since
, it follows that
. Since
, we conclude that the collection
is an SBE-path partition of D. So we may assume that P starts at
. Let w be the vertex in P that immediately follows
. Let
and let
. Let
. Since
, it follows that
. Since
, we conclude that the collection
is an SBE-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
be an arc of
. Then,
1) If
and
, then D admits an S-path partition,
2) If
and
, then D admits an S-path partition.
Proof. By the principle of directional duality, it suffices to prove (1). Let
. Since
, S is a maximum stable set in
. By hypothesis,
is α-diperfect. Let
be an S-path partition of
. Let P be a path in
such that
. Since
, it follows that P starts at
. Since
, the collection
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
,
, be a path of D such that
. If there exists a vertex u in
such that
and
, then D admits an S-path partition.
Proof. Let
. Let
. Since
, S is a maximum stable set in
. By hypothesis,
is α-diperfect. Let
be an S-path partition of
. Let R be a path in
such that
. Since
, it follows that R starts at u or
is an arc of R. If P starts at u, then since
, it follows that the collection
is an S-path partition of D. So suppose that
is an arc of P. Let
and
be the endvertices of R. Let
and let
. Thus the collection
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
be a path of D such that
. If there exists a vertex u in
such that
and
, 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
is an anti-P4 if
,
and
. Whenever it is convenient, we may write an anti-P4 as
. Since every anti-directed odd cycle and every blocking odd cycle of length at least five contains an induced anti-P4, it seems interesting to study digraphs that do not contain anti-P4 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-P4
in D, it follows that
(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
, 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
(resp.,
) the subset of
such that
(resp.,
). Moreover, let
, that is,
is a set of those vertices that both dominate and are dominated by some vertex in S (see Figure 4). Note that
,
and
are pairwise disjoint and since S is a maximum stable set in D, it follows that
.
Figure 4. Illustration of
,
and
.
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
and for every u in
, it follows that
and
.
Proof. Note that by the principle of directional duality, it suffices to show that
. Towards a contradiction, suppose that
. So let
be vertices in
. By definition of
, there exists a vertex y in S such that
. Since
and D is 3-anti-circulant, it follows that
, a contradiction because
. Thus
and
.
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
, 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
, then there exists no arc connecting vertices of distinct sets in
,
and
. Next, we show that
,
and
are stable. This implies that
, and hence, it follows by Lemma 10 that D satisfies the BE-property.
In the next three lemmas we show that if
contains a cycle C of length three such that C contains a digon and
, then D admits an SBE-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
be a digon in
. If there exists a vertex
in
such that
and
contains a
, then D admits an SBE-path partition.
Proof. With loss of generality, assume that
and
. Let
. Since
, S is a maximum stable set in
. By hypothesis,
is BE-diperfect. Let
be an SBE-path partition of
. Let P be a path in
such that
. If
, then the collection
is an SBE-path partition of D. So we may assume that
. By the principle of directional duality, we may assume that P starts at
. Let
. Next, we show by induction on k that
or
holds. First, suppose that
. Since
and D is 3-anti-circulant, it follows that
. Now, assume that
. By induction hypothesis,
or
for some
. Since
and
, it follows that
or
. Thus
or
. Since
, the collection
or
is an SBE-path partition of D.
From now on, we prove some results for 3-anti-circulant digraphs that belong to
.
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
be a digon in D. If
and there exists a vertex
in
such that
and
, then D admits an SBE-path partition.
Proof. The proof is divided into two cases depending on whether
or
. First, we prove the following claim.
Claim 1. If there exists a vertex
such
, then
is a complete digraph.
Since
,
and D is 3-anti-circulant, it follows that
. Since
, we conclude that
, and hence,
. Since
, it follows that
, and hence,
. Thus
is a complete digraph. This ends the proof of Claim 1.
Case 1.
. If
, then it follows by Claim 1 that
is complete, and hence, the result follows by Lemma 11. So
. If
(resp.,
), then since
and
, the result follows by Lemma 4 with
(resp.,
),
and
(resp.,
).
Case 2.
. Since
,
. We may assume by Lemma 11 that
and
. Thus it follows by Claim 1 that
. First, suppose that there exists a vertex
in
. Since
, it follows that
. Since
, we conclude that
. Since
, there exists at least one digon in
; otherwise,
is an induced transitive triangle. Since
and
, it follows that
. Thus the result follows by Lemma 11 applied to
. So we may assume that
. Let
. Since
,
,
,
and
, the result follows by Lemma 3 with
and
. 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
be a digon in D. If
and there exists a vertex
in
such that
and
, then D admits an SBE-path partition.
The following lemma states that we may assume that for every transitive triangle T in
,
.
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
and D contains a transitive triangle T such that
, then D admits an SBE-path partition.
Proof. Let
. Without loss of generality, assume that
and
. Since
, there exists at least one digon in T; otherwise, T is an induced transitive triangle. If
(resp.,
), then the result follows by Lemma 12 (resp., Lemma 13). Thus
. If
, then the result follows by Lemma 11. So
. Without loss of generality, assume that
. We show next that
. Suppose that there exists a vertex
in
. Since
and D is 3-anti-circulant, we conclude that
. Also, since
, it follows that
. Thus the result follows by Lemma 12 applied to
. So we may assume that
. Let
. Since
,
,
,
and
, the result follows by Lemma 3 with
and
. This finishes the proof.
The next lemma states that we may assume that
.
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
and there are vertices
and
such that
, then D admits an SBE-path partition.
Proof. By definition of
, there exists a vertex
in S such that
. By definition of
and
, there exists a vertex
in S such that
. Towards a contradiction, suppose that
. Since
and D is 3-anti-circulant, it follows that
, a contradiction because S is stable. So
, and hence, the result follows by Lemma 14 applied to
.
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
and there are
and
such that
, then D admits an SBE-path partition.
We show next that if
, then we may assume that
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
and
is not stable, then D admits an SBE-path partition.
Proof. Let
be adjacent vertices in
. Without loss of generality, assume that
. By definition of
, there are vertices
in S such that
and
. Since S is stable and D is 3-anti-circulant, it follows that
, and hence, the result follows by Lemma 14 applied to
.
The next lemma states that if D contains an anti-P4 disjoint from S, then D admits an SBE-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
and D contains an anti-P4 disjoint from S, then D admits an SBE-path partition.
Proof. Let
be an anti-P4 in D such that
. Since D is 3-anti-circulant, we conclude that
. We show next that
and
. Note that by the principle of directional duality, it suffices to show that
. Moreover, we may assume by Lemma 15 that
. Towards a contradiction, suppose that
. Since
, it follows that
. If
, then since
and
, we conclude that
. Since
, it follows that
, and hence,
, a contradiction by Lemma 9. If
, then since
, it follows by Lemma 17 that
. By Lemma 16,
. So
. Since
and
, it follows that
. By definition of
, there exists a vertex y in S such that
. Since
, we conclude that
, a contradiction because
. Thus
and
.
Now, let
and let
. Towards a contradiction, suppose that
and
. So let
vertices such that
in
and
in
. First, suppose that
. Since
, there exists at least one digon in
; otherwise,
is an induced transitive triangle. Since
and
, we conclude that
, and since
, the result follows by Lemma 16. So we may assume that
(see Figure 5(a)).
Figure 5. Illustration for the proof of Lemma 18.
Since
, we conclude that
. Since
,
. Also, since
, we conclude that
, and hence,
(see Figure 5(b)). Since
, it follows that
, a contradiction because
,
and
. Thus
or
. Since
, the result follows by Lemma 1 with
or by Lemma 2 with
.
In the next lemmas, we show that if
, then
and
are stable. To do this, we show that there exists no arc
in D such that
and
.
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
and there are adjacent vertices
in
such that
and
, then D admits an SBE-path partition.
Proof. By the principle of directional duality, we may assume that
. Also, we may assume by Lemma 15 that
. So
. By definition of
, there exists a vertex
in S such that
. By definition of
, there exists a vertex
in S such that
.
Claim 1.
.
Towards a contradiction, suppose that there exists
such that
. Since
and D is 3-anti-circulant, it follows that
, a contradiction by definition of
. Thus
. This finishes the proof of Claim 1.
If
, then since
, the result follows by Lemma 2 with
and
. So there exists a vertex
in
. By definition of
,
. By Claim 1,
. The rest of proof is divided into two cases depending on whether
or
.
Case 1.
. Recall that
with
. Since
, we may assume by Lemma 17 that
and
are non-adjacent. By definition of
, there exists a vertex
in S such that
. Towards a contradiction, suppose that
. Since
, we conclude that
, a contradiction because
. So
. Since
,
. Also, since
,
(see Figure 6).
Figure 6. Illustration for the proof of Lemma 19.
Claim 2.
.
By definition of
,
. Towards a contradiction, suppose that there exists a vertex
such that
for some
. Since
, we conclude that
, a contradiction because
. So
. This ends the proof of Claim 2.
Claim 3.
.
Towards a contradiction, suppose that there exists
such that
for some
. Then,
is an anti-P4 disjoint from S, and hence, the result follows by Lemma 18. So we may assume that
. This finishes the proof of Claim 3.
Claim 4. If there exists a vertex
in
such that
for some
, then
and
. Moreover,
.
Without loss of generality, assume that
. Since
,
. Since
, it follows by Lemma 17 that
(see Figure 7).
Figure 7. Illustration for the proof of Lemma 19.
By definition of
,
. Now, we show that
. First, suppose that
. Since
, there exists at least one digon in
; otherwise,
is an induced transitive triangle. Since
,
which contradicts Claim 3. So
. Now, let
be a vertex in
. By definition of
and since
, it follows that
. Since
, we conclude that
. Since
, we conclude that
. Thus since
and
, the result follows by Lemma 18. So
. If
for some
, then it follows by Lemma 1 with
and
that D admits an SBE-path partition. Thus
. Moreover, if
, then D contains an anti-P4 disjoint from S, and hence, the result follows by Lemma 18. Thus
. This ends the proof of Claim 4.
Claim 5. If
, then
.
Let
be a vertex in
. It follows by Claim 4 that
and
. Suppose that there exists a vertex
in
. By definition of
,
. Since
,
. Also, since
,
. Since
and
, it follows by Lemma 18 that D admits an SBE-path partition. So we may assume that
. This ends the proof of Claim 5.
The rest of proof is divided into two subcases depending on whether
or
.
Subcase 1.
. Let
be a vertex in
. It follows by Claim 4 that
and
. By Claim 5,
. Let
. Note that
is a source and
is a sink in
. Since
, S is a maximum stable set in
. By hypothesis,
is BE-perfect. Let
be an SBE-path partition of
. Let
be distinct paths in
such that
starts at
and
ends at
. Thus the collection
is an SBE-path partition of D.
Subcase 2.
. By Claim 3,
. Let
. Since
, S is a maximum stable set in
. Let
be an SBE-path partition of
. Let
be a path in
such that
and let
be a path in
such that
. In
,
. So it follows that both
and
have length one. If
ends at
or
ends at
, then since
and
, the collection
or
is an SBE-path partition of D. Thus
and
with
. Since
,
and
, we conclude that
and
. Thus the collection
is an SBE-path partition of D.
Case 2.
. By definition of
,
. If there exists a vertex
in
, then since
and
, the result follows by Lemma 18. Thus
, and hence, since
, the result follows by Lemma 1 with
and
. This ends the proof.
Now, we show that if
, then we may assume that there exists no arc
in D such that
and
.
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
and there are adjacent vertices
in
such that
and
, then D admits an SBE-path partition.
Proof. We may assume by Lemma 15 that
. So
. If
, then since
, the result follows by Lemma 2 with
and
. So there exists a vertex
in
. Since
,
. Since
,
. If there exists a vertex
in
, then since
and
, the result follows by Lemma 18. So we may assume that
. Since
, it follows by Lemma 1 with
and
that D admits an SBE-path partition. This finishes the proof.
We show next that we may assume that
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
and
is not a stable set, then D admits an SBE-path partition.
Proof. If there are adjacent vertices
in
such that
and
, then the result follows by Lemma 20. Let
be an arc in
. By the principle of directional duality, we may assume that
. Towards a contradiction, suppose that
. Let
be a vertex in
. By definition of
,
. Moreover, we may assume by Lemmas 20 and 19 that
. By definition of
, let y be a vertex in S such that
. Since
, we conclude that
, a contradiction by definition of
. Thus
. Since
, it follows by Lemma 2 with
and
that D admits an SBE-path partition.
Finally, we are ready for the main result of this subsection.
Theorem 2 Let D be a 3-anti-circulant digraph. If
, 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
is a proper induced subdigraph of D, then
is a 3-anti-circulant digraph, and hence, by the minimality of D, it follows that
satisfies the BE-property. Thus D does not satisfy the BE-property. It follows by Lemmas 17 and 21 that both
and
are stable. Thus it follows by Lemmas 19 and 20 that
is stable. Since S is a maximum stable set of D,
. 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
. 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
. Without loss of generality, assume that
and
. First, we prove some claims.
Claim 1.
. Moreover, if there exists
, then
and
.
Towards a contradiction, suppose that there are distinct vertices
in
. Since
and D is 3-anti-circulant, it follows that
. Since
, we conclude that
. Also, since
, it follows that
. Now, since
, it follows that
, and hence,
, a contradiction because
. Thus
. Moreover, note that if there exists
, then
and
. This ends the proof of Claim 1.
Claim 2.
.
Suppose that
. First, suppose that there exists a vertex
in
. By Claim 1, it follows that
,
and
. Let
. Since
, S is a maximum stable set in
. By hypothesis,
is α-diperfect. Let
be an S-path partition of
. Let P be a path in
such that
. Since
, it follows that P starts at
or
is an arc of P. If P starts at
, then since
and
, the collection
is an S-path partition of D (note that if
, then the result follows by previous argument). Thus
is an arc of P. Let
and
be the endvertices of P. Let
and
be the subpaths of P. Since
,
and
, the collection
is an S-path partition of D. So we may assume that
. This finishes the proof of Claim 2.
Claim 3.
.
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
. First, suppose that there exists a vertex
in
. By Claim 1, it follows that
,
and
. Let
and
. Since
,
and
, it follows by Lemma 7 that D admits an S-path partition. So we may assume that
.
Now, suppose that
. Since
, the result follows by Lemma 66. So we may assume that there exists a vertex w in
. Since
, we conclude that
. Let
and let
. Since
,
and
, 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-P4 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
. 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-P4 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-P4
, it follows that
and
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.