pipette
ENEnglish

Small and Large Quasi-Kernels in General Digraphs

Daniel Rutschmann

Preprint

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