A kernel of a digraph is a set of vertices which is both independent and absorbant. Let D be a digraph such that every proper induced subdigraph has a kernel. If D has a kernel, then D is kernel perfect, otherwise D is critical kernel-imperfect (for short CKI-digraph). In this work we prove that if a CKI-digraph D is not 2-arc connected, then D - a is kernel perfect for any bridge a of D. If D has no kernel but for all vertex x, D - x has a kernel, then D is called kernel critical. We give condi...
A kernel of a digraph is a set of vertices which is both independent and absorbant. Let D be a digraph such that every proper induced subdigraph has a kernel. If D has a kernel, then D is kernel perfect, otherwise D is critical kernel-imperfect (for short CKI-digraph). In this work we prove that if a CKI-digraph D is not 2-arc connected, then D - a is kernel perfect for any bridge a of D. If D has no kernel but for all vertex x, D - x has a kernel, then D is called kernel critical. We give conditions on a kernel critical digraph D so that for all x 2 V (D) the kernel of D-x has at least two vertices. Concerning asymmetric digraphs, we show that every vertex u of an asymmetric CKI-digraph D on n = 5 vertices satisfies d+(u) + d-(u) = n - 3 and d+(u), d-(u) = n - 5. As a consequence, we establish that there are exactly four asymmetric CKI-digraphs on n > 7 vertices. Furthermore, we study the maximum order of a subtournament contained in a not necessarily asymmetric CKI-digraph.