Small Quasi-kernel Conjecture and Large Quasi-kernel Conjecture
Every finite source-free digraph on vertices, meaning for every , has an independent set such that every vertex of is reachable from some vertex of by a directed path of length at most , and .
Equivalent formulations
Every finite source-free digraph on vertices has a quasi-kernel such that its closed out-neighbourhood satisfies . The cited source presents this assertion as equivalent to the Small Quasi-kernel Conjecture.
source: Ai, Gutin, Liu, and Meng, “Small and large quasi-kernels: a weighted transfer theorem”
References
- Small and large quasi-kernels: a weighted transfer theorem — arXiv — Jiangdong Ai, Gregory Gutin, Xiangzhou Liu, Xianhao Meng
Source: arXiv
Progress summary
A new paper links the two conjectures and proves a substantial special-case bound, but neither conjecture has been proved in full.
The small conjecture asks whether every digraph with no vertex of indegree zero has a quasi-kernel of size at most half its order. The large conjecture asks whether every sink-free digraph has a quasi-kernel whose closed in-neighborhood contains at least half the vertices; Erdős and Székely proposed the small conjecture in 1976.
Known results
- Chvátal–Lovász, 1974: every digraph has a quasi-kernel.
- Erdős–Székely, 1976: the small quasi-kernel conjecture was proposed.
- Kostochka, Luo, and Shan, 2022: the conjectures are equivalent and hold for orientations of -colorable graphs, including planar graphs.
- Ai, Liu, and Peng, 2024: the large conjecture implies only a -constant version of the small conjecture; both universal conjectures remain open.
October 2026 weighted transfer theorem
Jiangdong Ai, Gregory Gutin, Xiangzhou Liu, and Xianhao Meng claim a parameter-preserving weighted transfer theorem and use independent blow-ups to establish equivalence of the conjectures, with a half-order bound for source-free break digraphs. This is progress for the relationship and a special class, not a universal proof; the claim is unverified.
Current status (as of October 2026): Both universal conjectures remain open; the latest paper claims new equivalence and special-case results, but these are unverified.
Solutions 0
No solutions have been posted yet.