Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3

Abstract

A set is said to be a kernel if is an independent set and for every vertex there is a vertex such that . Let be a digraph such that every proper induced subdigraph of has a kernel. is said to be kernel perfect digraph (KP-digraph) if the digraph has a kernel and critical kernel imperfect digraph (CKI-digraph) if the digraph does not have a kernel. In this paper we characterize the asymmetric CKI-digraphs with covering number at most . Moreover, we prove that the only asymmetric CKI-digraphs with covering number at most are: , and . Several interesting consequences are obtained.