New extensions of kernel perfect digraphs to kernel imperfect critical digraphs (Q1343226)

Let \(D\) be a digraph and \(V(D)\) denote its vertex set. If \(K \subseteq V(D)\), then \(N^ -_ D(K)\) denotes the set of vertices in \(V(D) \setminus K\) which dominate at least one vertex of \(K\). A kernel of a digraph \(D\) is a subset \(K \subseteq V(D)\) such that \(K\) is independent (there are no arcs with both end vertices in \(K\)) and \(K \cup N^ -_ D = V(D)\). When every induced subdigraph of \(D\) has a kernel, \(D\) is said to be kernel-perfect. A kernel-perfect digraph \(D\) which does not have a kernel itself is said to be critical kernel-imperfect. The authors present a method to extend a kernel-perfect digraph to a critical kernel- imperfect digraph.