← All problems

Small Quasi-Kernel Conjecture; Large Quasi-Kernel Conjecture

Let D=(V,A)D=(V,A) be a sink-free digraph with ∣V∣=n|V|=n, meaning that every vertex has outdegree at least 11. A set Q⊆VQ\subseteq V is a quasi-kernel if QQ is independent and every vertex of DD is reachable from some vertex of QQ by a directed path of length at most 22. The small quasi-kernel conjecture asserts that DD has a quasi-kernel QQ with ∣Q∣≤n/2|Q|\le n/2. The large quasi-kernel conjecture asserts that DD has a quasi-kernel QQ such that its closed in-neighborhood N−[Q]=Q∪{v∈V:there is q∈Q with (v,q)∈A}N^-[Q]=Q\cup\{v\in V:\text{there is }q\in Q\text{ with }(v,q)\in A\} satisfies ∣N−[Q]∣≥n/2|N^-[Q]|\ge n/2.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 nn vertices has a quasi-kernel of size at most n/2n/2. The large conjecture asks for a quasi-kernel QQ whose closed in-neighborhood satisfies ∣N−[Q]∣≥n/2|N^-[Q]|\ge n/2; 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 44-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.

Sources

Solutions 0

No solutions have been posted yet.