Small and Large Quasi-Kernels in General Digraphs
In the authors' words
In a digraph , a set of vertices is a quasi-kernel if is an independent set and every vertex in can be reached from via at most two edges. The small quasi-kernel conjecture by Erd\H{o}s and Sz\'ekely predicts that every source-free -vertex digraph contains a quasi-kernel of size at most . Chv\'atal and Lov\'asz' 1974 work implies a bound of . In 2024, Sprio shows the bound . We show that there always is a quasi-kernel of size at most . For the related large quasi-kernel conjecture by Spiro, we show that there always is a quasi-kernel with .
Main resultThe abstract does not state a limitation.
Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: Preprint submitted to the Journal of Graph Theory