Critical Kernel Imperfectness in 4-quasi-transitive digraphs and 4-anti-transitive digraphs of small diameter
Germán Benítez-Bobadilla, Hortensia Galeana‐Sánchez, César Hernández‐Cruz · Discrete Applied Mathematics · 2025
A kernel in a digraph is an independent and absorbent subset of its vertex set. A digraph is critical kernel imperfect if it does not have a kernel, but every proper induced subdigraph does. In this article, we characterize asymmetrical 4-quasi-transitive and 4-transitive digraphs, as well as 2-anti-transitive, and asymmetrical 4-anti-transitive digraphs with bounded diameter, which are critical kernel imperfect.