Some sufficient conditions for the existence of kernels in infinite digraphs

A kernel N of a digraph D is an independent set of vertices of D such that for every w∈V(D)−N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. D is called a critical kernel imperfect digraph when D has no kernel but every proper induced subdigraph of D has a kernel. If F is a set of arcs of D, a semikernel modulo F of D is an independent set of vertices S of D such that for every z∈V(D)−S for which there exists an (S,z)-arc of D−F, there also exists an (z,S)-arc in D. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo F. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.     

A sufficient condition for kernel perfectness of a digraph in terms of semikernels modulo F

A kernel of a directed graph is a set of vertices which is both independent and absorbent. And a digraph is said to be kernel perfect if and only if any induced subdigraph has a kernel. Given a set of arcs F , a semikernel S modulo F is an independent set such that if some Sz-arc is not in F , then there exists a zS-arc. A sufficient condition on the digraph is given in terms of semikernel modulo F in order to guarantee that a digraph is kernel perfect. To do that we give a characterization of kernel perfectness which is a generalization of a previous result given by Neumann-Lara [Seminúcleos de una digrfica. Anales del Instituto de Matemticas 2, Universidad Nacional Autónoma de México, 1971]. And moreover, we show by means of an example that our result is independent of previous known sufficient conditions.