← All problems

Small Quasi-kernel Conjecture and Large Quasi-kernel Conjecture

Every finite source-free digraph DD on nn vertices, meaning dD−(v)≥1d_D^-(v)\ge 1 for every v∈V(D)v\in V(D), has an independent set Q⊆V(D)Q\subseteq V(D) such that every vertex of DD is reachable from some vertex of QQ by a directed path of length at most 22, and ∣Q∣≤n/2|Q|\le n/2.

Equivalent formulations
  1. Every finite source-free digraph DD on nn vertices has a quasi-kernel QQ such that its closed out-neighbourhood ND+[Q]=Q∪{v∈V(D):there exists u∈Q with u→v}N_D^+[Q]=Q\cup\{v\in V(D):\text{there exists }u\in Q\text{ with }u\to v\} satisfies ∣ND+[Q]∣≥n/2|N_D^+[Q]|\ge n/2. 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

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 44-colorable graphs, including planar graphs.
  • Ai, Liu, and Peng, 2024: the large conjecture implies only a 2/32/3-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.

Sources

Solutions 0

No solutions have been posted yet.