On the Small Quasi-kernel conjecture

Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei, Nika Salia, Mykhaylo Tyomkyn

Published 2023-07-09Version 1

The Chv\'atal-Lov\'asz theorem from 1974 establishes in every finite digraph $G$ the existence of a quasi-kernel, i.e., an independent $2$-out-dominating vertex set. In the same spirit, the Small Quasi-kernel Conjecture, proposed by Erd\H{o}s and Sz\'ekely in 1976, asserts the existence of a quasi-kernel of order at most $|V(G)|/2$ if $G$ does not have sources. Despite repeated efforts, the conjecture remains wide open. This work contains a number of new results towards the conjecture. In our main contribution we resolve the conjecture for all directed graphs without sources containing a kernel in the second out-neighborhood of a quasi-kernel. Furthermore, we provide a novel strongly connected example demonstrating the asymptotic sharpness of the conjecture. Additionally, we resolve the conjecture in a strong form for all directed unicyclic graphs.