Critical Kernel Imperfectness in $4$-quasi-transitive and $4$-anti-transitive digraphs of small diameter

Abstract

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.

arXiv comment20 pages