{"id":"arxiv/2610.29659","url":"https://arxiv.org/abs/2610.29659","tags":["math.CO"],"score":0,"title":"Small and Large Quasi-Kernels in General Digraphs","domain":"math.CO","source":"arxiv","authors":["Daniel Rutschmann"],"reviews":0,"subject":"math.CO","summary":"In a digraph $D$, a set $Q$ of vertices is a quasi-kernel if $Q$ is an independent set and every vertex in $D$ can be reached from $Q$ via at most two edges. The small quasi-kernel conjecture by Erdős and Székely predicts that every source-free $n$-vertex digraph contains a quasi-kernel of size at most $n - n/2$. Chvátal and Lovász' 1974 work implies a bound of $n - \\sqrt{n}+1$. In 2024, Sprio shows the bound $n - \\frac{1}{4} \\sqrt{n \\log_2 n}$. We show that there always is a quasi-kernel of size at most $n - \\frac{1}{51}n^{2/3} / \\ln^{2/3}(n)$. For the related large quasi-kernel conjecture…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-21","reactions":{}}