Infinite kernel perfect digraphs

Peer review under responsibility of Kalasalingam University.

Abstract

Let $D$ be a digraph, possibly infinite, V($D$) and A($D$) will denote the sets of vertices and arcs of $D$, respectively. A subset $K$ of V($D$) is said to be a kernel if it is both independent (a vertex in $K$ has no successor in $K$) and absorbing (a vertex not in $K$ has a successor in $K$). An infinite digraph $D$ is said to be a finitely critical kernel imperfect digraph if $D$ contains no kernel but every finite induced subdigraph of $D$ contains a kernel. In this paper we will characterize the infinite kernel perfect digraphs by means of finitely critical imperfect digraphs and strong components of its asymmetric part and then, by using some previous theorems for infinite digraphs, we will deduce several results from the main result. Richardson’s theorem establishes that if $D$ is a finite digraph without cycles of odd length, then $D$ has a kernel. In this paper we will show a generalization of this theorem for infinite digraphs.

Keywords:

• Infinite digraph
• Kernel
• Finitely critical kernel imperfect digraph

1 Terminology and introduction

For general concepts we refer the reader to [1] and [2]. We will say that two digraphs $D_1$ and $D_2$ are equal, denoted by $D_1=D_2$, if $A\left(D_1\right)=A\left(D_2\right)$ and $V\left(D_1\right)=V\left(D_2\right)$. A directed walk in a digraph $D$ is a sequence ($v_1,v_2,\dots ,v_n$) of vertices of $D$ such that $(v_i,v_{i+1})\in A\left(D\right)$ for each $i$ in $\{1,\dots ,n-1\}$. We will say that the directed walk $(v_1,v_2,\dots ,v_n)$ is closed if $v_1=v_n$. If $v_i\ne v_j$ for all $i$ and $j$ such that $\{i,j\}\subseteq \{1,\dots ,n\}$ and $i\ne j$, it is called a directed path. A directed cycle is a directed walk $(v_1,v_2,\dots ,v_n,v_1)$ such that $v_i\ne v_j$ for all $i$ and $j$ such that $\{i,j\}\subseteq \{1,\dots ,n\}$ and $i\ne j$. If $D$ is an infinite digraph, an infinite outward path is a sequence $(v_1,v_2,\dots )$ of distinct vertices of $D$ such that $(v_i,v_{i+1})\in A\left(D\right)$ for each $i\in \mathbb{N}$. In this paper we are going to write walk, path, cycle, instead of directed walk, directed path, directed cycle, respectively. Let $S_1$ and $S_2$ be subsets of V($D$), an arc ($u,v$) of $D$ will be called an $S_1{S}_2$-arc whenever $u$$\in$$S_1$ and $v\in S_2$.

For $S\subseteq V\left(D\right)$ the out-neighborhood (respectively in-neighborhood) ${\Gamma }_D^{+}$($S$) (respectively ${\Gamma }_D^{-}$($S$)) of $S$ is {$y\in V\left(D\right):(v,y)\in A\left(D\right)$ for some $v\in S$} (respectively $\{y\in V\left(D\right):(y,v\in A\left(D\right)\text{for some}v\in S\})$. A digraph $D$ is said to be outwardly finite if ${\Gamma }_D^{+}\left(\left\{v\right\}\right)$ is a finite set for every vertex $v$ in V($D$).

A digraph $D$ is said to be strong if for every pair of vertices $x$ and $y$ of $D$ there is an $xy$-path in $D$. A subdigraph $G$ of $D$ is called a strong component if it is strong and it is maximal with respect to this property. A strong component $G$ of $D$ is called initial (respectively terminal) if ${\Gamma }_D^{-}$(V($G$)) $\subseteq$ V($G$) (respectively ${\Gamma }_D^{+}$(V($G$)) $\subseteq$ V($G$)).

For $S\subseteq$ V($D$) the subdigraph of $D$ induced by $S$, denoted by $D$[$S$], has vertex set V($D$[$S$]) = $S$ and arc set $A$($D$[$S$]) = {($u,v$) $\in$$A$($D$) : {$u$, $v$} $\subseteq$$S$}. A subset $S$ of V($D$) is said to be independent if the only arcs in $D$[$S$] are loops.

An arc ($u,v$) in A($D$) is called asymmetric (resp. symmetric) if ($v,u$) is not in A($D$) (resp. ($v,u$) is in A($D$)). The asymmetric part of $D$, $Asymm$($D$), is the spanning subdigraph of $D$ whose arcs are the asymmetric arcs of $D$. A subdigraph of $D$ is asymmetric (symmetric) if all its arcs are asymmetric (symmetric).

A digraph $D$ is transitive whenever {($u,v$), ($v,w$)} $\subseteq$ A($D$) imply that ($u,w$) $\in$ A($D$). A digraph $D$ is called right-pretransitive (respectively left-pretransitive) whenever {($u,v$), ($v,w$)} $\subseteq$ A($D$) imply that {($u,w$), ($w,v$)} $\cap$ A($D$) $\ne$$0̸$ (resp. {($u,w$), ($v,u$)} $\cap$ A($D$) $\ne$$0̸$). A digraph $D$ is said to be quasi-transitive if {($u,v$), ($v,w$)} $\subseteq$ A($D$) imply that {($u,w$), ($w,u$)} $\cap$ A($D$) $\ne$$0̸$.

Let $D$ be a digraph. A subset $K$ of V($D$) is said to be a kernel if it is both independent (a vertex in $K$ has no successor in $K$) and absorbing (a vertex not in $K$ has a successor in $K$). The notion of kernel was introduced in [15] by von Neumann and Morgenstern in the context of Game Theory as a solution for cooperative $n$-player games. If every induced subdigraph of $D$ has a kernel, $D$ is said to be a kernel perfect digraph. Kernels have been widely studied. A nice survey on the subject is [8]. Chvátal proved in [4] that recognizing digraphs that have a kernel is an NP-complete problem in the context of finite digraphs, so finding sufficient conditions for a digraph to have a kernel or finding large families of digraphs with kernels has been a very prosperous line of investigation explored by many authors.

It is known that: every finite digraph without cycles is a kernel perfect digraph [15], every finite transitive digraph is a kernel perfect digraph [13]; if every cycle of a finite digraph $D$ has a symmetric arc, then $D$ is a kernel perfect digraph [3]; if $D$ is a finite digraph without odd cycles, then $D$ is a kernel perfect digraph [16], to name a few. However, this is not the case for infinite digraphs. In [17] R. Rojas-Monroy and I. Villarreal-Valdés considered the digraph $D^{\#}$ which has vertex set $V\left(D^{\#}\right)=\mathbb{N}$ and arc set $A\left(D^{\#}\right)=\{(i,j):i<j\}$. They observed that $D^{\#}$ is an infinite digraph which is transitive, asymmetric and without cycles (and therefore, without odd cycles) but this digraph is not kernel perfect. Notice that the kernel of a finite induced subdigraph of $D^{\#}$ is its vertex with the largest number, whereas every infinite induced subdigraph does not have a kernel, since there is no maximum of an infinite subset of $\mathbb{N}$. It is clear that the behavior of infinite digraphs with respect to kernels is different from the finite case. Some results for the existence of kernels in infinite digraphs are generalizable straightforward from their finite version; in other cases, adding a few new hypotheses will get the work done. An interesting class of digraphs without kernel are the critical kernel imperfect digraphs which are defined as follows: A digraph $D$ is said to be critical kernel imperfect if $D$ has no kernel but every proper induced subdigraph of $D$ has a kernel. A structural property of critical kernel imperfect digraphs, found by Berge and Duchet, is represented in Theorem 1.1.

Theorem 1.1

Berge and Duchet [3]

Let $D$ be a finite digraph. If $D$ is a critical kernel imperfect digraph, then $D$ is strong.

The following theorem is obvious, just take a minimal induced subdigraph with no kernel.

Theorem 1.2

Let $D$ be a finite digraph. If $D$ has no kernel, then $D$ contains an induced subdigraph which is critical kernel imperfect.

R. Rojas-Monroy and I. Villarreal-Valdés showed that Theorem 1.2 is not valid for infinite digraphs if we consider the digraph $D^{\#}$. They mention that it is not known whether there is an infinite digraph that is critical kernel imperfect but alternatively they give the concept of finitely critical kernel imperfect digraph as follows: an infinite digraph $D$ is said to be a finitely critical kernel imperfect digraph if $D$ contains no kernel but every finite induced subdigraph of $D$ contains a kernel. They proved the following theorem.

Theorem 1.3

[17]

Let $D$ be an infinite digraph that contains no kernel. Then $D$ contains an induced subdigraph which is either critical kernel imperfect or finitely critical kernel imperfect.

In [6] P. Duchet and H. Meyniel gave a characterization of the infinite kernel perfect digraphs but this characterization was only for outwardly finite digraphs. In this paper our main result consists in the characterization of infinite kernel perfect digraphs by using the concept of finitely critical kernel imperfect digraph. We will prove in Theorem 2.3 that if $D$ is a digraph (possibly infinite) and $\mathcal{S}$ the family of all strong components of $Asymm$($D$), then $D$ is a kernel perfect digraph if and only if (1) $D$[V($G$)] is a kernel perfect digraph for every $G$ in $\mathcal{S}$ and (2) $D$ contains no induced subdigraph which is finitely critical kernel imperfect. It is worth to mention that in [12] H. Galeana-Sánchez and V. Neumann-Lara established the finite version of the main result of this paper.

Among the classical results on the theory of kernels we have the following theorem.

Theorem 1.4

Richardson [16]

Let $D$ be a finite digraph without odd cycles. Then $D$ is a kernel perfect digraph.

Many extensions of Richardson’s theorem have been found over the years. For example, in [5] Duchet proved the following.

Theorem 1.5

Let $D$ be a digraph such that every odd cycle possesses at least two symmetric arcs, then $D$ is a kernel perfect digraph.

In Theorem 2.7 we will present the infinite version of Theorem 1.5 and as a direct consequence we will deduce Richardson’s theorem.

The following results will be useful in this paper because we will ask similar hypotheses on the induced subdigraph $D$[V($G$)] of $D$ for every $G$ in $\mathcal{S}$.

Theorem 1.6

[6]

Let $D$ be an outwardly finite digraph. $D$ is a kernel perfect digraph if and only if every finite induced subdigraph has a kernel.

Theorem 1.7

[9]

Let D be a strong digraph, possibly infinite. Then D is bipartite if and only if every cycle has even length.

Theorem 1.8

[10]

Let $D$ be a digraph, possibly infinite. Suppose that there exist two subdigraphs of $D$, say $D_1$ and $D_2$, such that $D=D_1\cup D_2$ (possibly A($D_1$ ) $\cap$ A($D_2$ ) $\ne$$0̸$ ), where $D_1$ is a right-pretransitive digraph, $D_2$ is a left-pretransitive digraph and $D_i$ contains no infinite outward path for $i$ in $\{1,2\}$. Then $D$ is a kernel perfect digraph.

Theorem 1.9

[11]

Let $D$ be a digraph (possibly infinite) such that $D=D_1\cup D_2$ (possibly $A\left(D_1\right)\cap A\left(D_2\right)\ne 0̸$ ), where $D_i$ is a quasi-transitive subdigraph of $D$ which contains no asymmetric (in $D$) infinite outward path. If every triangle contained in $D$ has at least two symmetric arcs, then $D$ is a kernel perfect digraph.

Theorem 1.10

[14]

Every bipartite digraph, finite or infinite, is a kernel perfect digraph.

Remark 1.11

[17]

Let $D$ be a nonempty digraph, possibly infinite. Let $\mathcal{S}$ be the family of all strong subdigraphs of $D$. We define a relation $\le$ on $\mathcal{S}$ by $S_1\le S_2$ if $S_1$ is a subdigraph of $S_2$. Then ($\mathcal{S},\le$) is a nonempty poset and it follows from Zorn’s Lemma that ($\mathcal{S},\le$) has a maximal element. Hence $D$ has at least one strong component.

Theorem 1.12

[17]

If $D$ is a symmetric digraph, finite or infinite, then D is a kernel perfect digraph.

Theorem 1.13

[17]

Let $D$ be a digraph, possibly infinite. Suppose that $D$ is a right-pretransitive or a left-pretransitive digraph such that every infinite outward path has a symmetric arc. Then $D$ is a kernel perfect digraph.

From now on all digraphs are possibly infinite (unless otherwise specified) and $\mathcal{S}$ the family of all strong components of $Asymm$($D$).

2 Main results

We will start with some results which are going to be useful.

Proposition 2.1

Let $D$ be a digraph. $D$ is strong if and only if for every partition of V($D$) into two subsets $\{V_1,V_2\}$there exist both a $V_1{V}_2$-arc and a $V_2{V}_1$-arc in $D$.

Proof

Let {$V_1,V_2$} be a partition of V($D$), $u$ in $V_1$ and $v$ in $V_2$. Since $D$ is strong, it follows that there exist a $uv$-path $P_1=(u=w_0,w_1,\dots ,w_n=v)$ and a $vu$-path $P_2=(v=z_0,z_1,\dots ,z_m=u)$. Let $i$ be the least positive integer such that $w_i\in V_2$ and $j$ the least positive integer such that $z_j\in V_1$. So, $w_{i-1}\in V_1$ and $z_{j-1}\in V_2$, which implies that both a $V_1{V}_2$-arc and a $V_2{V}_1$-arc exist in $D$.

Proceeding by contradiction, suppose that $D$ is not strong. Then there exists {$u,v$} $\subseteq$ V($D$) such that either there exists no $uv$-path or there exists no $vu$-path in $D$. Without loss of generality let us suppose there exists no $uv$-path in $D$.

Consider the sets $V_1$ = {$w$$\in$ V($D$) : there exists a $uw$-path} and $V_2$ = V($D$)$\setminus V_1$. Notice that {$V_1,V_2$} is a partition of V($D$) such that there exists no $V_1{V}_2$-arc in $D$ (because $V_1\cap V_2=0̸$), a contradiction.

Therefore, $D$ is strong. □

Lemma 2.2

Let $D$ be a digraph. If $D$ is a kernel imperfect digraph, then $\mathrm{Asymm}\left(D\right)$ is strong.

Proof

We proceed by contradiction, suppose that $Asymm$($D$) is not strong. It follows from Proposition 2.1 that there exists a partition $\{V_1,V_2\}$ of V($Asymm$($D$)) such that either there exists no $V_1{V}_2$-arc or there exists no $V_2{V}_1$-arc in $Asymm$($D$). Suppose without loss of generality that there exists no $V_1{V}_2$-arc in $Asymm$($D$).

Since $D$ is a kernel imperfect digraph and $D$[$V_1$] is a proper induced subdigraph of $D$, it follows that $D$[$V_1$] has a kernel $N_1$. Consider the subdigraph of $D$ induced by the set $V\left(D\right)\setminus (N_1\cup {\Gamma }_D^{-}\left(N_1\right))$ and call it $D_2$. Notice that $V\left(D\right)\setminus (N_1\cup {\Gamma }_D^{-}\left(N_1\right))\ne 0̸$, otherwise $N_1$ is a kernel of $D$ which is not possible. Let $N_2$ be a kernel of $D_2$ (there exists $N_2$ because $D_2$ is a proper induced subdigraph of $D$ and $D$ is a kernel imperfect digraph). Notice that $N_2\subseteq V_2$.

We claim that $N_1\cup N_2$ is a kernel of $D$.

We will prove that $N_1\cup N_2$ is an independent set in $D$.

Since $N_1$ and $N_2$ are independent sets in $D$, then it remains to prove that neither there exists $N_1{N}_2$-arc nor there exists $N_2{N}_1$-arc in $D$.

There exists no $N_2{N}_1$-arc in $D$ (because by construction of $D_2$ we have that V($D_2$) $\cap$${\Gamma }_D^{-}$($N_1$) = $0̸$). There exists no $N_1{N}_2$-arc in $D$, otherwise, if there exist $u$ in $N_1$ and $v$ in $N_2$ such that ($u,v$) is in A($D$), then ($u,v$) must be a symmetrical arc (because there exists no $V_1{V}_2$-arc in $Asymm$($D$)), which is not possible because there exists no $N_2{N}_1$-arc in $D$.

Therefore, $N_1\cup N_2$ is an independent set in $D$.

Since $V\left(D\right)=N_1\cup N_2\cup {\Gamma }_D^{-}\left(N_1\right)\cup {\Gamma }_{D_2}^{-}\left(N_2\right)$, it follows that $N_1\cup N_2$ is an absorbent set in $D$.

Therefore, $N_1\cup N_2$ is a kernel of $D$, which is a contradiction.

So, $Asymm\left(D\right)$ is strong. □

Next, we prove the main result.

Theorem 2.3

$D$ is a kernel perfect digraph if and only if (1) $D\left[V\left(G\right)\right]$ is a kernel perfect digraph for every $G$ in $\mathcal{S}$ and (2) $D$ contains no induced subdigraph which is finitely critical kernel imperfect.

Proof

Since $D$ is a kernel perfect digraph, it follows that (1) $D$[V($G$)] is a kernel perfect digraph for every $G$ in $\mathcal{S}$ (because every induced subdigraph of $D$[V($G$)] is an induced subdigraph of $D$) and (2) $D$ contains no induced subdigraph which is finitely critical kernel imperfect.

Proceeding by contradiction, suppose that $D$ is not a kernel perfect digraph. Then there exists a subset $I$ of V($D$) such that $D$[$I$] has no kernel.

We claim that $D$[$I$] contains a critical kernel imperfect digraph.

Consider two cases on $D$[$I$].

Case 1.$D$[$I$] is a finite digraph.

Since $D$[$I$] is a finite digraph without kernel, it follows from Theorem 1.2 that $D$[$I$] contains an induced subdigraph which is critical kernel imperfect.

Case 2.$D$[$I$] is an infinite digraph.

In this case we have that $D$[$I$] contains a finite induced subdigraph without kernel $D^{\prime }$ (because by hypothesis $D$ contains no induced subdigraph which is finitely critical kernel imperfect). So, it follows from Theorem 1.2 that $D^{\prime }$ has an induced subdigraph which is critical kernel imperfect.

Let $H$ be the induced subdigraph of $D$[$I$] such that $H$ is a critical kernel imperfect digraph. Then, it follows from Lemma 2.2 that $Asymm\left(H\right)$ is strong. Because of that $Asymm$($H$) is a subdigraph of $Asymm$($D$) (because $H$ is also an induced subdigraph of $D$) and it is strong, we have that there exists a strong component $G$ of $Asymm$($D$) such that $Asymm$($H$) is a subdigraph of $G$ (by Remark 1.11).

Claim.$H$ is an induced subdigraph of $D$[V($G$)].

Since V($H$) is a subset of V($D$[V($G$)]), it remains to prove that if {$u,v$} is a subset of V($H$) such that ($u,v$) $\in$ A($D$[V($G$)]), then ($u,v$) $\in$ A($H$).

Let {$u,v$} be a subset of V($H$) such that ($u,v$) $\in$ A($D$[V($G$)]). Then ($u,v$) $\in$ A($D$), which implies that ($u,v$) $\in$ A($D$[$I$]) (because {$u,v$} $\subseteq$ V($H$) $\subseteq$$I$). So, it follows that ($u,v$) $\in$ A($H$) (because $H$ is an induced subdigraph of $D$[$I$].

Since $D$[V($G$)] is a kernel perfect digraph (by hypothesis) and $H$ is an induced subdigraph of $D$[V($G$)], it follows that $H$ has a kernel, a contradiction.

Therefore, $D$ is a kernel perfect digraph. □

As a direct consequence of Theorem 2.3 we have the following results.

An independent subset $B$ of V($D$) is called quasi-kernel if for each vertex $v$ in V($D$)$\setminus B$ there is a path of length at most 2 from $v$ to some vertex of $B$. In [7] P.L. Erdős and L. Soukup proved the following.

Theorem 2.4

Let $D$ be a digraph. If $D$ has finite chromatic number then $D$ has a quasi-kernel.

With this result we can deduce that if $D$ is a transitive digraph with finite chromatic number then $D$ is a kernel perfect digraph (because in the case of transitive digraphs every quasi-kernel in $D$ is a kernel). So we get the following Corollary.

Corollary 2.5

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If for every $G$ in $\mathcal{S}$, $D$ [V($G$ )] is a transitive digraph with finite chromatic number, then $D$ is a kernel perfect digraph.

Proof

It follows from a combination of Theorems 2.4 and 2.3. □

Corollary 2.6

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If for every $G$ in $\mathcal{S}$, $D$ [V($G$ )] is bipartite, then $D$ is a kernel perfect digraph.

Proof

It follows from a combination of Theorems 1.10 and 2.3. □

Theorem 2.7

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If every odd cycle has at least two symmetric arcs, then $D$ is a kernel perfect digraph.

Proof

We will first prove that $D$[V($G$)] is a bipartite digraph for every $G$ in $\mathcal{S}$.

Let $G$ be in $\mathcal{S}$ and suppose that $\mid$V($G$)$\mid$$\ge 3$, otherwise $D$[V($G$)] already is bipartite.

Consider the following claims.

Claim 1.$G$ has no odd cycles.

Since $G$ is a subdigraph of $Asymm$($D$) and, by hypothesis, we have that every odd cycle in $D$ has at least two symmetric arcs, we conclude that $G$ has no odd cycles.

Claim 2.$G$ is a bipartite digraph.

Since $G$ is strong and it does not have odd cycles, it follows from Theorem 1.7 that $G$ is a bipartite digraph.

Let {$V_1$, $V_2$} be a partition of V($G$) in two independent sets in $G$.

Claim 3. {$V_1$, $V_2$} is a partition of V($G$) in two independent sets in $D$.

Proceeding by contradiction, suppose that $V_1$ is not an independent set in $D$. Then there exists a subset {$u$, $v$} of $V_1$ such that ($u,v$) $\in$ A($D$). Since $V_1$ is an independent set in $G$ and $G$ is a subdigraph of $Asymm$($D$), it follows that ($u,v$) is a symmetric arc in $D$. On the other hand, since $G$ is strong, we have that there exists a $uv$-path $P$ in $G$, notice that the length of $P$ is even. So, $P$$\cup$ ($v,u$) is an odd cycle with exactly one symmetric arc, a contradiction.

Therefore, $V_1$ is an independent set in $D$.

In the same way we can prove that $V_2$ is an independent set in $D$.

Therefore, since $D$[V($G$)] is a bipartite digraph for every $G$ in $\mathcal{S}$, it follows from Corollary 2.6 that $D$ is a kernel perfect digraph. □

Remark 2.8

We cannot omit in Theorem 2.7 the hypothesis “without induced subdigraph which is finitely critical kernel imperfect”. Consider that the digraph $D^{\#}$ (which was mentioned in the introduction) has the following properties:

1.	$D^{\#}$ has no kernel.

2.	Every finite induced subdigraph $G$ of $D^{\#}$ is transitive and therefore it has a kernel.

3.	Every odd cycle in $D^{\#}$ has at least two symmetric arcs (because $D^{\#}$ has no cycles).

From 1 and 2 it follows that $D^{\#}$ is a finitely critical kernel imperfect digraph.

Corollary 2.9

Richardson [16]

Let $D$ be a finite digraph without odd cycles. Then $D$ is a kernel perfect digraph.

Corollary 2.10

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If every odd cycle in $D$ [V($G$ )] has at least two symmetric arcs for every $G$ in $\mathcal{S}$, then $D$ is a kernel perfect digraph.

Corollary 2.11

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If $D$ [V($G$ )] is an outwardly finite digraph and every finite induced subdigraph of $D$ [V($G$ )] has a kernel for every $G$ in $\mathcal{S}$, then $D$ is a kernel perfect digraph.

Proof

It follows from a combination of Theorems 1.6 and 2.3. □

Corollary 2.12

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If $\left|V\left(G\right)\right|=1$ for every $G$ in $\mathcal{S}$, then $D$ is a kernel perfect digraph.

Corollary 2.13

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If $D$ [V($G$ )] is a right-pretransitive or a left-pretransitive digraph such that every infinite outward path has a symmetric arc for each $G$ in $\mathcal{S}$, then $D$ is a kernel perfect digraph.

Proof

It follows from a combination of Theorems 1.13 and 2.3. □

Corollary 2.14

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. If $D$ [V($G$ )] is a transitive digraph such that every infinite outward path has a symmetric arc for each $G$ in $\mathcal{S}$, then $D$ is a kernel perfect digraph.

Proof

It follows from Corollary 2.13. □

Corollary 2.15

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. Suppose that for each $G$ in $\mathcal{S}$there exist two subdigraphs of $D$ [V($G$ )], say $D_1$ and $D_2$, such that $D$ [V($G$ )] = $D_1\cup D_2$ (possibly $A\left(D_1\right)\cap A\left(D_2\right)\ne 0̸$ ), where $D_1$ is a right-pretransitive digraph, $D_2$ is a left-pretransitive digraph and $D_i$ contains no infinite outward path for $i$ in $\{1,2\}$. Then $D$ is a kernel perfect digraph.

Proof

It follows from a combination of Theorems 1.8 and 2.3. □

Corollary 2.16

Let $D$ be a digraph without induced subdigraph which is finitely critical kernel imperfect. Suppose that for each $G$ in $\mathcal{S}$there exist two subdigraphs of $D$ [V($G$ )], say $D_1$ and $D_2$, such that $D$ [V($G$ )] = $D_1\cup D_2$ (possibly $A\left(D_1\right)\cap A\left(D_2\right)\ne 0̸$ ), where $D_i$ is a quasi-transitive which contains no asymmetric (in $D$ [V($G$ )]) infinite outward path, and every triangle contained in $D$ [V($G$ )] has at least two symmetric arcs. Then $D$ is a kernel perfect digraph.

Proof

It follows from a combination of Theorems 1.9 and 2.3. □

Notes

Peer review under responsibility of Kalasalingam University.