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.
