Infinite kernel perfect digraphs

Abstract

Let be a digraph, possibly infinite, V() and A() will denote the sets of vertices and arcs of , respectively. A subset of V() is said to be a kernel if it is both independent (a vertex in has no successor in ) and absorbing (a vertex not in has a successor in ). An infinite digraph is said to be a finitely critical kernel imperfect digraph if contains no kernel but every finite induced subdigraph of 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 is a finite digraph without cycles of odd length, then 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