Small quasi-kernels in directed graphs
Is it true that if D=(V,A) is a digraph where every node has positive out-degree, then D has a quasi-kernel of size at most |V|/2?
This conjecture was proposed by P. L. Erdős and L. A. Székely in 1976. It is a well-known result of Chvátal and Lovász  that every digraph has a quasi-kernel. An example of a digraph without a sink that does not have two disjoint quasi-kernels can be found in the paper of Gutin, Koh, Tay and Yeo . Heard and Huang  proved that several classes of graphs (semicomplete multipartite, quasi-transitive, and locally semicomplete) contain two disjoint quasi-kernels.
- V. Chvátal, L. Lovász, Every directed graph has a semi-kernel, Lecture Notes in Math 411 (1974), 175. DOI link.
- G. Gutin, K. M. Koh, E. G. Tay, A. Yeo, On the number of quasi-kernels in digraphs, Journal of Graph Theory 46 (2004), 48-56. DOI link. Author link.
- S. Heard, J. Huang, Disjoint quasi-kernels in digraphs, DOI link.