Towards the Small Quasi-Kernel Conjecture

Let $D=(V,A)$ be a digraph. A vertex set $K\subseteq V$ is a quasi-kernel of $D$ if $K$ is an independent set in $D$ and for every vertex $v\in V\setminus K$,$v$isatmostdistance2from$K$. In 1974, Chv'atal and Lov'asz proved that every digraph has a quasi-kernel. P. L. Erd\H{o}s and L. A. Sz'ekely in 1976 conjectured that if every vertex of $D$ has a positive indegree, then $D$ has a quasi-kernel of size at most $\mathrm{\mid }V\mathrm{\mid }\mathrm{/}2$. This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasi-transitive, or locally demicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4-colorable graphs (in particular, of all planar graphs).