2024/06/07 by Jiangdong Ai, Ai, Jiangdong, Xiangzhou Liu +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2406.04887
openalex publication_date 2024/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A quasi-kernel of a digraph D is an independent set Q such that every vertex can reach Q in at most two steps. A 48-year conjecture made by P.L. Erdős and Székely, denoted the small QK conjecture, says that every sink-free digraph contains a quasi-kernel of size at most n/2. Recently, Spiro posed the large QK conjecture, that every sink-free digraph contains a quasi-kernel Q such that |N-[Q]|≥ n/2, and showed that it follows from the small QK conjecture. In this paper, we establish that the large QK conjecture implies the small QK conjecture with a weaker constant. We also show that the large QK conjecture is equivalent to a sharp version of it, answering affirmatively a question of Spiro. We formulate variable versions of these conjectures, which are still open in general. Not many digraphs are known to have quasi-kernels of size (1-α)n or less. We show this for digraphs with bounded dichromatic number, by proving the stronger statement that every sink-free digraph contains a quasi-kernel of size at most (1-1/k)n, where k is the digraph's kernel-perfect number.