Small Quasi-Kernel Conjecture; Large Quasi-Kernel Conjecture
Let be a sink-free digraph with , meaning that every vertex has outdegree at least . A set is a quasi-kernel if is independent and every vertex of is reachable from some vertex of by a directed path of length at most . The small quasi-kernel conjecture asserts that has a quasi-kernel with . The large quasi-kernel conjecture asserts that has a quasi-kernel such that its closed in-neighborhood satisfies .
References
- Small and Large Quasi-Kernels in General Digraphs — arXiv — Daniel Rutschmann
Source: arXiv
Progress summary
New work improves the best known bounds for both conjectures, but neither conjecture has been resolved.
The small conjecture, attributed to Erdős and Székely in 1976, asserts that every sink-free digraph on vertices has a quasi-kernel of size at most . The large conjecture asks for a quasi-kernel whose closed in-neighborhood satisfies ; both remain open in general.
Known results
- Chvátal and Lovász (1974): every digraph has a quasi-kernel.
- Kostochka, Luo, and Shan (2022): the small conjecture holds for several restricted classes, including orientations of -colorable graphs.
- Ai, Gerke, Gutin, Yeo, and Zhou (2023): the small conjecture holds for generalized anti-claw-free digraphs, including sink-free one-way split digraphs.
- Ai, Liu, and Peng (2024): the small conjecture implies the large one; both remain open, with further bounds for kernel-perfect digraphs.
October 2026 advance
Daniel Rutschmann's article reports an improved upper bound for small quasi-kernels and a new coverage estimate for the large conjecture, moving both results toward their conjectured linear-scale conclusions. This is claimed progress, not a resolution, and the mathematical claims have not been independently assessed here.
Current status (as of October 2026): Both conjectures remain open; an October 2026 article claims improved bounds for each, but those advances are unverified.
Solutions 0
No solutions have been posted yet.