Small and Large Quasi-Kernels in General Digraphs
En palabras de los autores
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 .
Resultado principalEl resumen no menciona limitaciones.
Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: Preprint submitted to the Journal of Graph Theory