Towards the small quasi-kernel conjecture (Q2088687)

Summary: 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\) is at most distance 2 from \(K\). \textit{V. Chvatal} and \textit{L. Lovász} [Lect. Notes Math. 411, (1974; Zbl 0297.05116)] proved that every digraph has a quasi-kernel. P. L. Erdős and L. A. Székely in 1976 conjectured that if every vertex of \(D\) has a positive indegree, then \(D\) has a quasi-kernel of size at most \(|V|/2\). This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasi-transitive, or locally semicomplete 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).