# Small quasi-kernels in directed graphs

From Egres Open

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*?

## Remarks

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 ^{[1]} 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 ^{[2]}. Heard and Huang ^{[3]} proved that several classes of graphs (semicomplete multipartite, quasi-transitive, and locally semicomplete) contain two disjoint quasi-kernels.

## References

- ↑ 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.