Small and Large Quasi-Kernels in General Digraphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.29659
curl -X POST /api/v1/records/arxiv/2610.29659/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.29659/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'